Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Delphi Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 16   вперед  Ctrl
 TDictionary или TList<>.BinarySearch с позиции поиска  [new]
серчер
Guest
Миллион сортированных строк (MSSQL ORDER BY ASC):
str: varchar(12), value: int

Str - фиксированной длины, то есть все строки всегда одной длинны и содержат только цифры.

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

Что хотелось бы - скорости в поиске и отсутствия большого объема данных в памяти.

В настоящий момент я использую TList<>.BinarySearch.
Comparer конкретно в данном случае выглядит примерно так:
  Result := CompareStr(L.Str, R.Str);


Но есть другие места, где в схожей задаче comparer выглядит так
  Result := CompareStr(L.Str, R.Str);
  if Result = 0
    Result := CompareStr(L.Secondary, R.Secondary);
  if Result = 0
    REsult := ValueSign(L.Code, R.Code);


Вторичный вопрос:
Имеет ли особый смысл приведения строковых данных, например, к а) хешу и б) инту (интам), кодируя каждый байт строки?
13 дек 16, 19:33    [19999270]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
rgreat
Member

Откуда:
Сообщений: 3022
Как вариант - разбей гигантский лист на несколько поменьше.
И данные в них раздели например по MOD от хэша.
13 дек 16, 19:44    [19999293]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1926
серчер,

Хеш быстрее сортированного списка или тем более дерева
В чём вопрос - я так и не понял
13 дек 16, 20:37    [19999445]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
makhaon
Member

Откуда: Дальнее замкадье
Сообщений: 1253
серчер,

может базе отдать базово и не заниматься творческим онанизмом?
13 дек 16, 20:45    [19999472]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
серчер
Guest
SOFT FOR YOU,

хеш - это же строка в любом случае, нет?
12 символов против 20, а в чем тогда выгода?

Это выше вопросы - раз. и два - стоит ли вместо строк хранить хеш в листе и все это делать самому, или, например, воспользвоаться TDictionary - он же сам это все (в тч бинарный поиск) делает или нет?


makhaon
может базе отдать базово

Ну давайте рассуждать
а) много потоков
б) в пике до 50 серчей в секунду.
в) миллион записей (это порядок цифр, а не точное значение).

Что лучше - затрахать базу по ТСР или использовать память и проц сервера?
Допустим выбираем "затрахать базу по ТСР". Что сделать? Все строки привести к чему? Или построить индекс по тексту?

rgreat, это уже перебор. Не понятно, что это даст.
13 дек 16, 21:12    [19999551]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
defecator
Member

Откуда: arm-pascal.ru
Сообщений: 31525
серчер
SOFT FOR YOU,

хеш - это же строка в любом случае, нет?

нет
13 дек 16, 21:14    [19999554]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
makhaon
Member

Откуда: Дальнее замкадье
Сообщений: 1253
серчер,

ой, да ладно, напугал базу миллионом записей )

>в пике до 50 серчей в секунду.

гугл посмотри, и ничего - справляется. весь вопрос в базе, железе и запросах. вообще, я для себя давно вывел простое правило. базы не зря придумали. и алгоритмы для них десятилетиями пилили. и довольно мало шансов, что у себя получится сделать лучше.
поэтому всем поиском должна заниматься база. только нужно её нормально настроить и запросы написать.
впрочем - дело твоё, конечно.
13 дек 16, 21:22    [19999570]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
rgreat
Member

Откуда:
Сообщений: 3022
серчер
rgreat, это уже перебор. Не понятно, что это даст.

Если сделаешь 10 листов вместо одного то искать придется не в миллионе записей а в ста тысячах.
Что явно быстрей.
И это все почти бесплатно.

Опять-таки добавление объекта в маленький сортированый лист будет работать на порядок быстрей чем в большой.
13 дек 16, 21:25    [19999579]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
makhaon
Member

Откуда: Дальнее замкадье
Сообщений: 1253
серчер,

автор
Что лучше - затрахать базу по ТСР или использовать память и проц сервера?


к слову - а чё её трахать? если у тебя изменяемых записей почти нет? кидай данные на сторону базы и пусть она там в себе ковыряется сама.
13 дек 16, 21:25    [19999580]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
серчер
Guest
defecator, приведите пример класса с хеш-переменной, какой у нее будет тип?
13 дек 16, 21:35    [19999608]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
серчер
Guest
makhaon
серчер,

ой, да ладно, напугал базу миллионом записей )

>в пике до 50 серчей в секунду.

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


Там были еще вопросы или мимо прошли вопросы? :) А я бы почитал ответы :)
13 дек 16, 21:36    [19999617]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
rgreat
Member

Откуда:
Сообщений: 3022
серчер
defecator, приведите пример класса с хеш-переменной, какой у нее будет тип?
Тип может быть любой.
От байта до строки.
13 дек 16, 21:37    [19999619]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
серчер
Guest
Господа, а что вы скажете про TDictionary vs TList<> в плане использования для поиска?
13 дек 16, 21:37    [19999622]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
серчер
Guest
rgreat
серчер
defecator, приведите пример класса с хеш-переменной, какой у нее будет тип?
Тип может быть любой.
От байта до строки.


Разумеется. Какой в данном случае подойдет?
13 дек 16, 21:39    [19999626]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
rgreat
Member

Откуда:
Сообщений: 3022
серчер,

TDictionary по любому быстрей, но могут быть рандомные просадки быстродействия во время его роста.
И на TDictionary надо больше памяти.
13 дек 16, 21:40    [19999628]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
makhaon
Member

Откуда: Дальнее замкадье
Сообщений: 1253
серчер,

Вот - такие у меня для тебя ответы :)
13 дек 16, 21:40    [19999629]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
asviridenkov
Member

Откуда:
Сообщений: 3638
серчер
Господа, а что вы скажете про TDictionary vs TList<> в плане использования для поиска?


Ищет быстро. Хэши долго делает.
13 дек 16, 21:40    [19999632]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
rgreat
Member

Откуда:
Сообщений: 3022
серчер,

Обычно используют 4 байта. А что подойдет вам - это ваше решение.
13 дек 16, 21:41    [19999636]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
серчер
Guest
makhaon,
да я так и понял, что никаких, кроме блаблабла :)


asviridenkov, спасибо


rgreat, мой случай это строка из 12 символов. 12 байт.
13 дек 16, 22:15    [19999796]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1926
серчер
Господа, а что вы скажете про TDictionary vs TList<> в плане использования для поиска?


Скажу - замути тест и сам замерь производительность
13 дек 16, 22:18    [19999814]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
Квейд
Member

Откуда: Kyiv, Ukraine
Сообщений: 4762
серчер
хеш - это же строка в любом случае, нет?
Нет, конечно. Результат простой хеш-функции CRC32 это integer
15 дек 16, 00:55    [20005109]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
серчер
Guest
makhaon
серчер,

Приходишь на публичный форум - будь готов к любым ответам.


Всё взаимообратно. Отвечаешь что хочешь, ведешь себя непотребно или говоришь не по теме - ты никому нравиться не обязан.

Квейд
В рамках Дельфи?
15 дек 16, 16:02    [20008016]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
white_nigger
Member

Откуда: Тула
Сообщений: 1295
серчер
Всё взаимообратно. Отвечаешь что хочешь, ведешь себя непотребно или говоришь не по теме - ты никому нравиться не обязан.
Вообще-то он всё правильно говорил. Кури матчасть. Хэш может быть какой угодно, чаще всего целочисленное число
15 дек 16, 17:23    [20008476]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 1926
Ну че там по тестам то?
16 дек 16, 12:35    [20011250]     Ответить | Цитировать Сообщить модератору
 Re: TDictionary или TList<>.BinarySearch с позиции поиска  [new]
серчер
Guest
SOFT FOR YOU
Пока не делал.
Лучшим решением все таки было бы хеш сделать. Только не очень понятно чем воспользоваться, чтобы к инту привести вот такие строки

D6999900001
D6999900002
A6999900003
F6999900004
....

И затем сравниваемое (которое может входить или не входить в данный набор) так же приводить к уникальному инту и по нему сравнивать.
16 дек 16, 17:31    [20013450]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 16   вперед  Ctrl
Все форумы / Delphi Ответить