Ускорение сравнения строк

Автор: Madjack

Сам столкнулся с этой проблемой недавно. Может это и не ново, но возможно не все это знают, а если и знают, то не учитывают.

Суть проблемы: если в вашей программе (в частном случае в игре) производится многократное сравнение строк примерно 20-30 тысяч раз в секунду, это не есть хорошо. Большинство конечно понимает, что все это легко и просто заменяется идентификатором целого типа. НО. В данном случае затрудняется читабельность кода при дебагинге. Тобишь надо все время рыться в списках соответсвий дабы понять, что это за объект с таким вот id. Некоторые думают так - "Я не потеряю в скорости ничего, если буду сравнивать строки вместо идентификаторов, так как у меня мало сравнений и вообще потом все переделаю". Обычно, потом количество объектов экспоненциально возрастает, а переделывать становится лень.

Ближе к делу... Я тут написал простенький классик, который хранит в себе строковые идентификаторы, но сравнивает их целые значения типа __int64. Преобразовывает к целому значению в момент присваивания нового значения, с последующей возможностью получить строковый эквивалент. Но есть небольшое ограничение строки в 16 символов.

Вот, собственно, сам клас.

qstring.h

#pragma once

#define QSTRING_MAXCHAR  16

class qstring
{
  char container[QSTRING_MAXCHAR];
  __int64  value;

protected:
  void HashValue( void );

public:
  qstring( void );
  qstring( const char* );
  ~qstring(void);

  void SetValue( const char* );
  const char* GetValue( void ) const;
  const __int64 Value( void ) const { return value; }
  void Clear( void );
  bool Empty( void );

  operator __int64 ( ) const;
  operator const char* ( ) const;
  bool operator == ( qstring v ) const;
  bool operator == ( int v ) const;
  bool operator != ( qstring v ) const;
  qstring& operator = ( const char* v );

  bool operator < ( qstring v ) const
  {
    return v.value < value;
  }

  bool operator > ( qstring v ) const
  {
    return v.value > value;
  }

  bool operator <= ( qstring v ) const
  {
    return v.value <= value;
  }

  bool operator >= ( qstring v ) const
  {
    return v.value >= value;
  }
};

qstring.cpp

#include "qstring.h"
#include <Windows.h>

qstring::qstring(void)
{
  memset(container, 0, QSTRING_MAXCHAR);
  value = 0;
}

qstring::qstring( const char* v )
{
  memset(container, 0, QSTRING_MAXCHAR);
  SetValue( v );
}

void qstring::Clear( void )
{
  memset(container, 0, QSTRING_MAXCHAR);
  value = 0;
}

bool qstring::Empty( void )
{
  return value == 0;
}

qstring::~qstring(void)
{
}

void qstring::SetValue( const char* v )
{
  // Save string value
  int str_len = (int)strlen(v);
  if (str_len > QSTRING_MAXCHAR)
    str_len = QSTRING_MAXCHAR;

  value = 0;

  strncpy( container, v, str_len );

  // Hash string value into __int64
  int c = 0;
  for (int i=0; i < str_len; i++)
  {
    if ( i % 2 )
      value = value + (container[i] << c);
    else
    {
      value = value + ((container[i]*2) << c);
      c++;
    }
  }
}

const char* qstring::GetValue( void ) const
{
  return container;
}

qstring::operator __int64 ( ) const
{
  return value;
}

qstring::operator const char* ( ) const
{
  return container;
}

bool qstring::operator == ( qstring v ) const
{
  return v.value == value;
}

bool qstring::operator == ( int v ) const
{
  return v == value;
}

bool qstring::operator != ( qstring v ) const
{
  return v.value != value;
}

qstring& qstring::operator = ( const char* v )
{
  SetValue( v );
  return *this;
}

Для ускорения работы класса можно перенести частоиспользуемые функции в inline.

Вот собственно и все, чем я хотел поделиться. Если кто может предложить более эффективный алгоритм хэширования строки в целое с более длинными строками, то я только за. Присылайте свои предложения.

2 октября 2003