оптимальна скорость доступа к массиву

← →
brother © (2012-12-14 09:54) [0]

есть массив:
TValue = array [0..DictValueLength - 1] of byte; TItem = record Value: TValue; Count: Int64; end; TItems = array of TItem;

нужно организовать работу с массивом: добавление, быстрый поиск по Value.
Вот думаю, как это все оптимальнее сделать, массив будет большой (Int64 или сколь хватит оперативы)...
Есть предложения?

← →
TUser © (2012-12-14 09:57) [1]

Предлагаю использовать хэш-таблицу вместо массива.

← →
brother © (2012-12-14 10:00) [2]

1. думаю сортировать все добавляемое
2. делать выборку (для поиска) в пределах по Value[0] значениям
3. что еще?

← →
brother © (2012-12-14 10:00) [3]

да о хэше думаю тож...

← →
БарЛог © (2012-12-14 10:02) [4]

> 1. думаю сортировать все добавляемое

Ужас какой

← →
DVM © (2012-12-14 10:07) [5]

> БарЛог © (14.12.12 10:02) [4]
> > 1. думаю сортировать все добавляемое
>
> Ужас какой

Это почему это ужас? Если список изначально отсортирован (а надо использовать именно список, а не массив), то каждая вставка в нужное место списка с использованием бинарной сортировки занимает очень малое время, тоже относится и к поиску. Главное сделать функцию сравнения для TValue. Сравнимо с хэш таблицами, реализация же проще значительно.

← →
БарЛог © (2012-12-14 10:35) [6]

DVM © (14.12.12 10:07) [5]

> Сравнимо с хэш таблицами, реализация же проще значительно.

Ну если так - беру слова обратно.

← →
Dimka Maslov © (2012-12-14 10:58) [7]

> DVM © (14.12.12 10:07) [5]

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

← →
брат Птибурдукова (2012-12-14 11:19) [8]

> brother © (14.12.12 09:54)

uses Generics.Collections;
type
TItems = TDictionary<TValue, Int64>;

← →
brother © (2012-12-14 11:26) [9]

← →
Ega23 © (2012-12-14 11:50) [10]

Зависит от операций. Если вставок не много, то сортируй. Если вставки - то, наверное, лучше хэш.

← →
brother © (2012-12-14 12:15) [11]

втавок куча! практически на каждой итерации обращения к массиву...
видимо буду юзать хеш...

← →
DVM © (2012-12-14 12:34) [12]

> brother © (14.12.12 12:15) [11]

Ты бы взял и сравнил хэш таблицы и списки на своих данных, а потом уже решил. А то мечешься от одного к другому.
У хэш таблиц есть свои недостатки, если что.

А собственно, сколько элементов всего планируется? И куча вставок это сколько в секунду?

← →
brother © (2012-12-14 12:39) [13]

да, пока только теория...
как только проведу практические тесты, буду дальше спрашивать)

← →
brother © (2012-12-14 12:39) [14]

только надо озадачиться хэш коллизиями и их учесть...

← →
Ega23 © (2012-12-14 12:54) [15]

Реши, чего больше: вставок или выборок.

← →
MBo © (2012-12-14 13:21) [16]

подкину ещё вариант организации словаря - radix tree

← →
брат Птибурдукова (2012-12-14 13:25) [17]

Помню, в древней книжке по бейсику описывалась эмуляция бинарных деревьев на массиве. Имхо вставка в отсортированное дерево + двоичный поиск для описанной задачи — самое то.

← →
Pavia © (2012-12-14 14:14) [18]

> нужно организовать работу с массивом: добавление, быстрый
> поиск по Value.Вот думаю, как это все оптимальнее сделать,
> массив будет большой (Int64 или сколь хватит оперативы).
> ..Есть предложения?

Возьми книжку по алгоритмам и почитай. А то из твоего условия ничего ни ясно.
А посему наиболее оптимальным будет взять структуру с наиболее средними показателями, а именно B-деревья.

← →
Pavia © (2012-12-14 14:18) [19]

> Вот думаю, как это все оптимальнее сделать, массив будет
> большой (Int64 или сколь хватит оперативы)...

Есть золотое правило. У программистов оно звучит так. Проигрываешь в памяти выигрываешь в скорости. Проигрываешь в скорости выигрываеь в памяти.

Почему именно оперативной памяти почему жёсткий диск не использовать?

← →
Sha © (2012-12-14 14:29) [20]

> brother © (14.12.12 09:54)
> Есть предложения?

чтобы были предложения обо всем,
сначала нужно это все конкретизировать

← →
картман © (2012-12-14 16:06) [21]

> Sha © (14.12.12 14:29) [20]

у меня есть такая же или очень похожая задачка, поэтому напишу здесь:

есть данные
TMyRec = record
key1: Integer;
key2: Integer;
Value: Double;
end;

записей много. Добавляем, удаляем и ищем много. Нужны операции "удалить все записи по key1" и то же по key2.

← →
Jeer © (2012-12-14 16:32) [22]

TableInMemory

← →
картман © (2012-12-14 16:40) [23]

> TableInMemory

что это? Можно ссылочку на описание?

← →
Jeer © (2012-12-14 17:00) [24]

Таблица аля базы данных, но в памяти.
В зависимости от реализации - поддержка индексов, SQL-запросов и пр.
Из того, что у Вас под руками - ClientDataset.

← →
картман © (2012-12-14 17:11) [25]

> Jeer © (14.12.12 17:00) [24]

спасибо, но, думаю, скорость маловата будет

← →
брат Птибурдукова (2012-12-14 17:15) [26]

Ещё у гансмокера была описана забавная методика работы с файлами FILE_FLAG_DELETE_ON_CLOSE + FILE_ATTRIBUTE_TEMPORARY

← →
Sha © (2012-12-14 18:09) [27]

> картман © (14.12.12 16:06) [21]
> Добавляем, удаляем и ищем много.

мне пару раз найти очки - это очень много

как работаем?

одну добавляем, потом одну ищем, потом одну удаляем, итд
или
добавили 1000000, ищем 1000, удаляем 1, еще ищем, еще удаляем, итд

по ключам примерно поровну
или
по одному ключу 1000 раз, по другому 1

еще какие-то особенности есть?

← →
картман © (2012-12-14 18:36) [28]

сначала добавляем 100 млн
ищем минимальное значение среди Values, извлекаем key1 и key2
удаляем все записи для key1 и key2. (примерно по 10 тыс)
добавляем 10 тыс
примерно так

или, лучше так:

M = (x11, x12, .. x1N)
(x21, x22, ..x2N)
...
xN1, xN2, ..xNN)

массив треугольный, получаемый пеермноженим одномерного самого на себя. Т.е. выглядит так:
M = (x11, x12, .. x1N)
(x21, x22, ..NULL)
...
xN1, NULL, ..NULL)

нашли xIJ, удаляем I-й столбец и J-ю строку, потом нужно добавить строку из N-1 элементов

можно удалять не на каждой итерации. Зависит от доступной памяти.

> массив треугольный, получаемый пеермноженим одномерного
> самого на себя.

главная диагональ тоже нулевая

> массив треугольный, получаемый пеермноженим одномерного самого на себя.

как получаются поля элемента X[i,j]?

> потом нужно добавить строку из N-1 элементов

куда? и что делаем потом?

> как получаются поля элемента X[i,j]?

сравнением данных i-го и j-го элементов

> куда?

куда угодно(удобней)

> и что делаем потом?

удаляем все данные, касающиеся Key1 и Key2, т.е. в случае с массивом:
DelRow([Key1, Key2]);
DelCol([Key1, Key2]);

генерим новый элемент, вставляем:
for Key in data
AddInArray(NewKey, Key);

Если ничего из предложенного другими участниками форума не подходит, то предлагаю то, что уже предложили. Перестроение индексов при обращении к данным на чтение и сброс/обновление индексов при изменении данных.

> Владислав © (14.12.12 23:14) [32]

не устроит быстродействие.
Всем спасибо, вопрос закрыт. Можно обойтись без перераспределения памяти и индексов))

после [17] считаю оффтопом, ибо не уточнено, что не понятно в моей формулировке...

зы. зная пользователей данного форума и их любительство к оффтопу - необходимую инфу для алгоритмов я уже подчерпнул со страниц данного топика, конкретно [5].
Иван, зачем флудим с [19]?

спасибо остальным за размышления - задумался!

← →
Студент (2012-12-17 18:07) [38]

Может двунаправленный список, отсортированный и поиск элемента дихотомией?

← →
брат Птибурдукова (2012-12-17 18:48) [39]

Какая такая дихотомия в связных списках?

+ накладные расходы довольно солидные

пока остановился на вот таком варианте:

... TValue = array [0..DictValueLength - 1] of byte; TItem = record Value: TValue; Count: Int64; CRC32: cardinal; end; TItems = array of TItem; ... Dict: array [0..255] of TItems; ... procedure TXXX.ItemAdd(Value: TValue); procedure _Add(id: byte; Value: TValue; crc: cardinal); begin SetLength(Dict[id], High(Dict[id])+2); Dict[id][High(Dict[id])].Value:= Value; Dict[id][High(Dict[id])].Count:= 0; Dict[id][High(Dict[id])].CRC32:= crc; end; var n: int64; max: int64; crc: cardinal; id: byte; begin id:= Value[0]; max:= High(Dict[id]); crc:= GetCRC32(Value); if max > 0 then begin n:= 0; repeat // anee crc niaiaaa?o e ia eieeecey if (crc = Dict[id][n].CRC32) and (CompareMem(@Dict[id][n].Value, @Value, DictValueLength)) then begin Inc(Dict[id][n].Count); Exit; end; Inc(n); until n > Max; _Add(id, Value, crc); end else _Add(id, Value, crc); end; ...
для тестов алгоритмов, скорость устраивает...

оптимальна скорость доступа к массиву Найти похожие ветки