|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Dashkovsky 2:5002/46.4 15 Mar 2002 19:37:10
To : Alexey Shirshin
Subject : Индекс и поиск
--------------------------------------------------------------------------------
12 Мар 02 19:42, you wrote to me:
AS> Есть массив, элементы котоpого записи. Каждая запись из 10 полей.
AS> Как быстpо осyществлять поиск по каждомy из полей?
AS> Какие есть ваpианты?
AS> Размеp массива пpимеpно 500 Мб.
Если делать руками и без СУБД, я делал это так:
обычное двоичное дерево, где 2х4 - указатель на лево и право, ещё 4 - указатель
на реальную структуру в памяти и последние 4 - какаянь-дь хеш-сумма этой
структуры. Далее заполнял это дерево оно влезало в 500 кил. Сами данные весили
мег 5-10мег. Далее при построении строил дерево по эток контрольной сумме, если
суммы равны - извлекал реальную структуру, тем самым экономил время на
сравнениях. Всё это я делал ещё в реальном режиме через драйвер расширенной
памяти, память выделял блоками по 512к, была своя система адресации номер блока
и смещение внутри блока, на защищённом режиме можно упростить. Дерево
располагалось линейно в памяти, а указатель на лево и направо был в виде номера
очередной записи дерева в массиве. Потом правда после построения дерева я его
вытягивал в массив в 2 этапа: 1) проставлял вместо кеша указатель на корень, 2)
- обходил дерево в нужном порядке и формировал новый массив указателей, как бы
линейный индекс, эта процедура делалась очень быстро. Узкое место тут в
контрольной сумме, по которой делать первоначальное сравнение, т.к. я на неё
отводил 4 байта и если делать хорошую сумму - теряется сортировка, если делать
чтобы сортировка не терялась - растут потери на сравнениях.
Почему-то двоичное дерево порядка n - мне не понравилось, может у меня алгоритм
был кривой, но когда большой порядок - долго, а когда маленький - смысл его
теряется, хотя если обычное двоичное дерево будет сбалансированно - эффекту
должно быть больше.
Andrey
... Любишь кататься - люби и катайся!
--- GoldED+/386 1.1.4.7
* Origin: Всёфигня кроме пчёл,хотя пчёлы,еслиподумать,тоже фигня (2:5002/46.4)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
Быстpее, быстpее, быстpее неплохо было бы... если можно |
Eugene Vestin |
02 Mar 2002 04:59:01 |
 Re: Быстpее, быстpее, быстpее неплохо было бы... если можно |
Andrew Doroshev |
03 Mar 2002 19:30:46 |
  Re: Быстpее, быстpее, быстpее неплохо было бы... если можно |
Eugene Vestin |
04 Mar 2002 17:11:54 |
 Re: Быстpее, быстpее, быстpее неплохо было бы... если можно |
Alexey Goloborchy |
05 Mar 2002 11:15:05 |
|
Re: Быстpее, быстpее, быстpее неплохо было бы... если можно |
Andrew Doroshev |
05 Mar 2002 12:58:07 |
|
Быстpее, быстpее, быстpее неплохо было бы... если можно |
Andrey Dashkovsky |
02 Mar 2002 13:43:18 |
|
Быстpее, быстpее, быстpее неплохо было бы... если можно |
Eugene Vestin |
05 Mar 2002 02:17:23 |
|
Быстpее, быстpее, быстpее неплохо было бы... если можно |
Alexandr Brezgin |
03 Mar 2002 05:50:00 |
|
Быстpее, быстpее, быстpее неплохо было бы... если можно |
Eugene Vestin |
04 Mar 2002 17:18:23 |
|
Re: Быстpее, быстpее, быстpее неплохо было бы... если можно |
Alexey Goloborchy |
05 Mar 2002 11:00:38 |
|
Быстpее, быстpее, быстpее неплохо было бы... если можно |
Alexandr Brezgin |
08 Mar 2002 00:22:00 |
|
Все пpосто замечательно |
Eugene Vestin |
09 Mar 2002 05:02:45 |
|
Все пpосто замечательно |
Alexandr Brezgin |
13 Mar 2002 01:47:00 |
|
Все пpосто замечательно |
Eugene Vestin |
14 Mar 2002 13:25:04 |
|
Быстpее, быстpее, быстpее неплохо было бы... если можно |
Alex Cvetkov |
02 Mar 2002 11:51:35 |
|
Быстpее, быстpее, быстpее неплохо было бы... если можно |
Eugene Vestin |
04 Mar 2002 17:07:58 |
|
Быстpее, быстpее, быстpее неплохо было бы... если можно |
Alex Cvetkov |
05 Mar 2002 11:35:06 |
|
Быстpее, быстpее, быстpее неплохо было бы... если можно |
Eugeny Malkov |
06 Mar 2002 09:48:35 |
|
Быстpее, быстpее, быстpее неплохо было бы... если можно |
Alex Cvetkov |
07 Mar 2002 01:29:07 |
|
Куда уж быстpее :). Стpуктуpы индексаций? |
Eugene Vestin |
09 Mar 2002 05:09:21 |
|
Быстpее, быстpее, быстpее неплохо было бы... если можно |
Andrey Dashkovsky |
09 Mar 2002 17:14:23 |
|
Re: Быстpее, быстpее, быстpее неплохо бы ло бы... если можно |
Andrew Ezhguroff |
12 Mar 2002 17:41:58 |
|
Индекс и поиск |
Alexey Shirshin |
12 Mar 2002 20:42:16 |
|
Re: Индекс и поиск |
Sergey Andrianov |
20 Mar 2002 20:20:04 |
|
Индекс и поиск |
Andrey Dashkovsky |
15 Mar 2002 19:37:10 |
|
|
