привет!
не знаю сюда писать или в алгоритмы. начну с "сюда", так как задача имеет несколько подзадач.

условия :
нужно подобие std::map
ключ — GUID
значение — пока строка, может ещё что-то добавится.
кол-во — более 50 000 элементов
VC++ 6.0

сложности:
во-первых много элементов
во-вторых GUID как ключ... боюсь медленный поиск по нему будет

вопросы:
можно ли использовать какой-нить map(из стандартной поставки, стороний)? проверял ли кто нить быстродействие на таких объёмах?
какой хэш можно сделать из GUID

Заранее спасибо!
Денис

PS если нужно что-то пояснить — welcome

Здравствуйте, Denis, Вы писали:

D>условия :
D>нужно подобие std::map
D>ключ — GUID
D>значение — пока строка, может ещё что-то добавится.
D>кол-во — более 50 000 элементов
D>VC++ 6.0

D>сложности:
D>во-первых много элементов
D>во-вторых GUID как ключ... боюсь медленный поиск по нему будет

Реальный опыт
Число элементов — больше 5 млн.
Ключ 40 байт отображается на 4 байта

Это индексация содержимого файла.

STLPort 4.5.3(?), BCB5.

Не могу сказать, что работает медленно.

Здравствуйте, Denis, Вы писали:

Прежде всего, я бы не стал называть контейер на 50000 элеметнов "очень большим".

D>сложности:
D>во-первых много элементов
Отнюдь
D>во-вторых GUID как ключ... боюсь медленный поиск по нему будет
Бояться надо будет, когда профайлер испугается

D>вопросы:
D>можно ли использовать какой-нить map(из стандартной поставки, стороний)? проверял ли кто нить быстродействие на таких объёмах?

Используй std::map. Если при тестах профайлер покажет, что std::map тормозит, тогда надо начинать искать замену. Можно будет например попробовать hash_map из STLPort.

D>какой хэш можно сделать из GUID

Да хоть все тот же старый добрый CRC32

D>PS если нужно что-то пояснить — welcome
Какие операции преобладают?

Здравствуйте, Denis, Вы писали:

D> нужно подобие std::map
D> ключ — GUID
D> значение — пока строка, может ещё что-то добавится.
D> кол-во — более 50 000 элементов

Для 50 000 элементов, мапу потребуется не более log2(50000) сравнений.
Вычислив логарифм из этого числа, ты удивишся, что поличилось около число в
пределах 16.

Если тебя такая вещь не устраивает, можешь попробовать хеш-таблицу.

---------------------------------------------------------
СНП, Артёмов Денис. e-mail: artyomov <at> inbox.ru

Здравствуйте, Denis, Вы писали:

D>условия :
D>нужно подобие std::map
D>ключ — GUID
D>значение — пока строка, может ещё что-то добавится.
D>кол-во — более 50 000 элементов
D>VC++ 6.0

D>сложности:
D>во-первых много элементов
D>во-вторых GUID как ключ... боюсь медленный поиск по нему будет

std::map именно по GUID размером около 100 000 элементов был мной реально использован. Тормозов не наблюдалось. Рекомендую на скорую руку построить тестовую программу ...

Здравствуйте, ArtDenis, Вы писали:

AD>Для 50 000 элементов, мапу потребуется не более log2(50000) сравнений.
AD>Вычислив логарифм из этого числа, ты удивишся, что поличилось около число в
AD>пределах 16.

А можешь тогда быстренько на пльцах объяснить, как она это делает? За 16 сравнений всего?

Здравствуйте, Scrambler, Вы писали:

S>А можешь тогда быстренько на пльцах объяснить, как она это делает? За 16 сравнений всего?
Зайди на algolist.manual.ru и почитай про красно-черные деревья.
И вобще про алгоритмы и структуры данных.

Здравствуйте, Scrambler, Вы писали:

S>А можешь тогда быстренько на пльцах объяснить, как она это делает? За 16 сравнений всего?

Во первых, я имел ввиду доступ к элементу мапа по индексу.
Во вторых, как правило, реализация мапа основана на структуре красно-чёрного дерева. Подобная струкура данных позволяет осуществлять быстрый поиск узла дерева.
В третих, я тут немного ошибся. Максимальное количество сравнений для поиска будет не 16, а 32, т.к. максимальная высота красно-чёрного дерева вычисляется по формуле 2log(n+1)
В четвёртых, если тебе интересно, как организуются деревья поиска, можешь в строке поисковика набрать "красно-чёрное дерево", "деревья поиска" или "сбалансированные деревья".

Денис.

Здравствуйте, Коваленко Дмитрий, Вы писали:

КД>Здравствуйте, Denis, Вы писали:

D>>сложности:
D>>во-первых много элементов
D>>во-вторых GUID как ключ... боюсь медленный поиск по нему будет

КД>Реальный опыт
КД>Число элементов — больше 5 млн.
КД>Ключ 40 байт отображается на 4 байта

КД>Это индексация содержимого файла.

Мда, вот поставили мне оценку. А я ведь тебя обманул

• это оказался не map, а set
  
• индексирует он действительно 40 байт, но хранит DWORD, который указывает на элемент в "сегментном" файле.

Вот в файле как раз и хранятся эти 40 байтные уникальные идентификаторы.

Для этого извращения написан собственный класс сравнения вида

struct TRPL_ObjectKeyIndexComparer
{
 public: //typedefs
  typedef TRPL_ObjectKeyData                        key_type;
  typedef size_t                                    size_type;

  typedef size_type                                 index_type;

  struct tag_key_loader
  {
   virtual void load(index_type index,key_type& key)=0;
  };

 public:
  //ldr - это загрузчик 40-байтных идентификаторов
  TRPL_ObjectKeyIndexComparer(tag_key_loader& ldr)
   :m_ldr(ldr)
  {;}

 public:
  //[i1]<[i2]
  bool operator () (const index_type i1,const index_type i2)const;
  {
   key_type i1_key;
   m_ldr.load(i1,i1_key);//загружаем аргумент с левой стороны

   key_type i2_key;
   m_ldr.load(i2,i2_key);//загружаем аргумент с правой стороны

   return i1_key.compare_key(i2_key)<0;
  }//i1,i2

 private:
  tag_key_loader& m_ldr;
};//struct TRPL_ObjectKeyIndexComparer

//объявление set' а выглядит так
typedef TRPL_ObjectKeyIndexComparer                  tag_element_comparer;
typedef set<index_type,tag_element_comparer>         tag_element_storage_indexes;

КД>Не могу сказать, что работает медленно.
Тормозов действительно особо не наблюдаю. На P4-2.4 512MB

Вот. Признался перед товарищами в обмане (возможно ребенка) и сразу полегчало

А то взял умножил 40*5млн получил 200MB. Перепугался, полез смотреть и не увидел такого пожирания памяти

КД>Вот. Признался перед товарищами в обмане (возможно ребенка) и сразу полегчало
КД>А то взял умножил 40*5млн получил 200MB. Перепугался, полез смотреть и не увидел такого пожирания памяти

так-так... за обман можно попинать больно ... за "ребёнка" тоже пожалуй... но могу и помиловать если скажешь расход памяти на твоё кол-во элементов.

Здравствуйте, Denis, Вы писали:


КД>>Вот. Признался перед товарищами в обмане (возможно ребенка) и сразу полегчало
КД>>А то взял умножил 40*5млн получил 200MB. Перепугался, полез смотреть и не увидел такого пожирания памяти

D>так-так... за обман можно попинать больно ... за "ребёнка" тоже пожалуй... но могу и помиловать если скажешь расход памяти на твоё кол-во элементов.

Фух. Спасибо что дали возможность исправиться.

Реально не могу сказать сколько оно жрет памяти именно под set. Эксперимент ставить тоже — прям щас — не получится. Могу сказать только сколько отожрала вся программа, когда в нее засунули в районе 5-6млн элементов. Где-то около 180MB.

Так в принципе 4байта данные+2*4байта под left-right указателей дерева (на базе которого построен std::set). 12*5000000=60MB

Вроде так.