Автор Тема: Разобраться с 100000000 строк  (Прочитано 15167 раз)

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Разобраться с 100000000 строк
« Ответ #45 : Апрель 06, 2012, 08:30:47 pm »
Посмотрел http://waqur.livejournal.com/445417.html
Кстати, я когда хэштаблицу увеличиваю, то хэшкоды от ключей не перевычисляю  :) :) :) Просто с самого начала я вычисляю хэшкод h не по модулю длины таблицы N, а целый uint, то есть по модулю 2^32 и запоминаю его. Естественно индексируюсь по индексу i = h mod N. Затем, когда N увеличивается до N' мне не нужно перевычислять хэшкоды от объектов, а достаточно просто индексироваться по i' = h mod N'. Более того, когда ищу элемент в списке линейным поиском, то сначала проверяю равенство полных uint-ных хэшкодов и лишь если они равны (вероятность случайного совпадения одна четырёхмиллиардная), то проверяю на точное равенство ключи. Летает со скоростью света.

DIzer

  • Гость
Re: Разобраться с 100000000 строк
« Ответ #46 : Апрель 06, 2012, 08:39:32 pm »
я про это и написал.. когда давал общую схему расчета Петру - она очевидна (я не имею в иду расширение таблицы) - в этой задаче это ВОЗМОЖНО но НЕРАЗУМНО а вот если хранить не 10 лимонов 20 байтных строк а 8 байтные числа с плавающей точкой - то ВПОЛНЕ  :)
« Последнее редактирование: Апрель 06, 2012, 08:43:45 pm от DIzer »