Есть ли такой алгоритм?

Возможно ты имеешь в виду хэштаблицу.

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

могу тебе первый элемент найти со скоростью независящей от количества записей в таблице
или любой по счету, в таблице с записями одинакового размера
;)

Скорость поиска никак не может _не зависеть_ от кол-ва записей. И обязательно нужно более детально описать процесс поиска. Скажем, если ты ищешь по точному совпадению X1, и на искомом поле существует индекс, то при поиске анализироваться будут только записи, содержащие X1, соответственно. А вот если ты скажем будешь искать по какому-нибудь регэкспу, то тут не учитывать все записи просто нельзя (можно, конечно, но это уже отдельная история). Если короче – нужна конкретика.

Возможно плохо описал, поэтому пример: Есть две таблицы в которых в первом столбце - имя и фамилия человека, а во втором его номер телефона. В первой таблице 10^7 строк и в ней только у 2-х людей имя Александр, только у 2-х имя Алексей. По счету в таблице эти имена располагаются рандомно. Я ввожу в поиск «лекс» и мне выводятся имена и номера этих людей (с учётом того, что в таблице нет больше людей у которых в имени или фамилии содержится «лекс»). Вторая таблица содержит 10^12 строк, в ней есть только 1 Александр и 3 Алексея, расположенных в рандомных местах таблицы. Я ввожу в поиск «лекс» и мне выводятся имена и номера этих людей с такой же скрорстью как и в первой таблице (с учётом того, что в таблице нет больше людей у которых в имени или фамилии содержится «лекс»).

Привел пример https://www.linux.org.ru/forum/development/12692268?cid=12692378 (комментарий)

Что значит «с такой же скоростью»? Если вам нужно уменьшить затраты на поиск, и вы уверены среди каких записей нужно искать, можно сначала отсортировать записи, а потом искать. Но конкретно в вашем примере все 10кк записей из первой таблицы не нужны будут, если у вас данные проиндексированы. Анализироваться будут только 4 записи, плюс время на поиск, собственно, индекса.

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

А если уж прямо имена - то тебе нужен инверсный индекс. Конкретно твой случай - взять какой нибудь солр/сфинкс, в зависимости от религии, и проиндексировать. Или если РСУБД - можно взять постгрес, построить индекс по ts_vector, тоже достаточно быстрая реализация.

Т.е. в общем случае - ответ инверсный индекс, если действительно интересны случаи когда много повторяющихся данных. В частности, если речь действительно идет о быстром поиске по тексту - это lucene/solr/sphinx.

Есть. Trie, succinct data structures - копай в этом направлении

В первом сообщении про матчинг по подстроке ничего не было, а так бы хэш таблица с perfect hash тебе бы подошла. А с подстрокой смотри trie. Тебе нужно построить префиксное дерево всех суффиксов, поиск будет за O(длина строки), независимо от объёма данных.

Оно в любом случае зависит от числа элементов. Другое дело - характер этой зависимости. У того же бинарного поиска логарифмическая, но данные должны быть упорядочены.

Да, спасибо. Это то, что я искал.

А да. На будущие - trie, если это не сжатые его вариации, которые дальше описал пацан - стоит тысячи памяти особенно в твоих пхп. Там на каждую ноду будет 2кило памяти, а дальше уже все зависит от разряженности данных. И 2кило это не в пхп.

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

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

Я недавно делал СУБД и для поиска как-раз изпользовал trie, никаких сверх потреблений памяти не было (во время тестирования), trie был сохранён в файл, а читал я его через mmap.

особенно в твоих пхп

Упаси бог, от этого языка держусь за километр.

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

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

Я недавно делал СУБД и для поиска как-раз изпользовал trie, никаких сверх потреблений памяти не было (во время тестирования), trie был сохранён в файл, а читал я его через mmap.

trie стоит 1кб на каждый шаг уникального пути для ascii, если у тебя флаг хранится в указателе.

Т.е. нода будет:

struct node_t {
  node_t * childs[128];
};

У меня на /usr/share/dict/words бревно весит почти гиг.

Ты либо тестил как все тестировщики на килобайте, либо использовал какой-то сжатый вариант.

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

Ну допереть до n-ного бревна, где n длинна алфавита не такое уже и достижение.

Ну ладно - не надо так не надо.

Вторая таблица содержит 10^12 строк,
В первой таблице 10^7 строк
Неизвестный размер данных
full-text поиск

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

Давайдосвидания.

Давайдосвидания.

Кукареку.

Если ли такой алгоритм, который позволяет искать некий элемент в таблице, со скоростью независящей от количества записей в таблице?
Последнее исправление: Taetricus 24.06.2016 21:24:59
Скорость поиска никак не может _не зависеть_ от кол-ва записей.
(24.06.2016 21:07:18)

Т.е. ты ответил до уточнения, каким хреном ты оправдываешь себя тем, что было после?

И да, подстроки такие же строки и ничего не мешает сделать бревно по всем подстрокам.

И да, подстроки такие же строки и ничего не мешает сделать бревно по всем подстрокам.

Ну дак да. Тебе, конечно, не мешает. Вперде :)

Т.е. ты ответил до уточнения, каким хреном ты оправдываешь себя тем, что было после?

Откуда ты это вывел, гений логики? Я сказал, дословно, по слогам, для тебя:

Скорость поиска
Ско-ро-сть по-ис-ка

Т.е. ты ответил до уточнения

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

Ну дак да. Тебе, конечно, не мешает. Вперде :)

Т.е. ты обделался. Ты высрал:

Скорость поиска никак не может _не зависеть_ от кол-ва записей.

Потом начал кукарекать:

full-text поиск
Поэтому trie

Давайдосвидания.

Но т.к. ты ламерюга, ты в очередной раз обделался и trie может точно так же в подстроки со скоростью не зависимой от n.

Откуда ты это вывел, гений логики? Я сказал, дословно, по слогам, для тебя:

Попытки амёбки съехать настолько убоги.

Скорость поиска

Да, скорость поиска не зависит от кол-ва данных. Там O(m) хоть для мильёна, хоть для мильярда.

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

Ты не предположил - ты ответил хернёй, а потом попытался оправдаться тем, что бревно по строкам не может в поиск по подстрокам, но тут ты то же обделался, ибо может.

Ты обычная ламерюга которая кроме мапы из жабки ничего не знает и на этом был основан твой первый высер.

Даже если мы предположим, что ты реально предположил, то я точно так же могу предположить.

Да, скорость поиска не зависит от кол-ва данных. Там O(m) хоть для мильёна, хоть для мильярда.

Ты болезный, почему ты называешь trie и КА – поиском? Если ты достаешь элемент по ключу, это для тебя тоже поиск, поехавший?

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

И снова, болезный, где я это _утверждал_?

Даже если мы предположим, что ты реально предположил, то я точно так же могу предположить.

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

Ты болезный, почему ты называешь trie и КА – поиском?

Опять сливы. Меня не интересуют твои потуги - ты либо отвечай по тебе, либо убеги в страхе из темы.

Спащу тебе тот пример, который ты пастил мне:

Есть две таблицы в которых в первом столбце - имя и фамилия человека, а во втором его номер телефона.
Я ввожу в поиск «лекс» и мне выводятся имена и номера этих людей

Изначальное условие:

Если ли такой алгоритм, который позволяет искать некий элемент в таблице

Поиск в таблице есть поиск по индексу, где значение поля - есть ключ, а ссылка на таблицу - значение.

И снова, болезный, где я это _утверждал_?

Вот тут про скорость поиска:

Скорость поиска никак не может _не зависеть_ от кол-ва записей.

Далее потуги в адрес trie:

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

Давайдосвидания.

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

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

Давай ещё раз, дебилушка. Было дано условие - искать по полю таблицу. Не было указано по полному ключу, либо по подстроке.

Ты начал оправдывать свой высер тем, что видите-ли ты предположил поиск по подстрокам(хотя это не работает и я тебя обоссал уже и по подстрокам) - на что я ответил тем же - «я предположил поиск по целому ключу».

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

Поиск в таблице есть поиск по индексу, где значение поля - есть ключ, а ссылка на таблицу - значение.

С чего ты решил что это _обязательно_ должен быть _поиск по индексу_? Ты предполагаешь, царек? Дак так и пиши :)

Далее потуги в адрес trie:

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

Все правильно. Это не потуги, это громкий смех в зале над твоим способом реализации trie, не более.

Было дано условие - искать по полю таблицу.

Искать по полю таблицу? Ты опять таблеток не доел, или просто в словах уже от пуканоразрыва путаешься?

(хотя это не работает и я тебя обоссал уже и по подстрокам)

На данный момент ты «обоссал» только сам себя.

Царь в этом треде прав.

Прав в чем? :)

В том, что поиск подстроки в строке можно сделать независимым от длинны этой строки, если игнорировать время чтения с диска/оперативной памяти.

В том, что поиск подстроки в строке можно сделать независимым от длинны этой строки, если игнорировать время чтения с диска/оперативной памяти.

А где вы вместе с царем увидели, что я это отрицаю, можно узнать?

Есть ли такой алгоритм? (комментарий)

Скорость поиска никак не может _не зависеть_ от кол-ва записей.

Я говорил именно о _поиске_, а не о получении по ключу а-ля хэш-таблица или trie. И с trie царь залез потом. Так что не понимаю как из этого вы делаете вывод что я говорил о

поиск подстроки в строке можно сделать независимым от длинны этой строки

Вы говорите не о поиске, а о элементарном _получении значения по ключу_. Пора бы уже различать.

Т.е. поиск строки в подстроке это не поиск? Хватит юлить.

Я уже четко и ясно сказал – trie – это получение значения по ключу. Ты _не ищешь_ «бла» в «бла-бла-бла», ты берешь значение «бла-бла-бла» по определенному ключу (который может быть и запросом). Поиск подразумевает _перебор_ вариантов. И где ты увидел юлешь, умник?

Давай сюда определение «поиска» в твоём понимании.

Я же написал.

Поиск подразумевает _перебор_ вариантов.

И да, если я говорю: «я хочу получить [n-ый] элемент массива», то не считаю это поиском. Доступ по ключу – это доступ по ключу, и не важно, хэш-таблица это, или ключи в виде [n-1]...[n-k] в префиксном дереве.

А вот тот же бинарный поиск, это поиск или как? Мы там варианты не перебираем, однако всегда называем его поиском...

«Двоичный поиск» это как-бы просто _название алгоритма_. Ну называется алгоритм так, что поделать. Но ты же не скажешь, что поиск (просто поиск) – это алгоритм? Нет, конечно же. Поиск может работать по тому или иному алгоритму(мам), но сам по себе это не алгоритм. Как и большая разница с trie. Trie – всего навсего _структура данных_ для быстрого доступа, и к поиску не имеет никакого отношения.

Поражение засчитано. Для будущих поколений по поводу срача выше - скорость доступа к mysql и postgres (комментарий)

Как я люблю лор.

Т.е. примерно в 750тысяч раз быстрее твоего результата на луа с мускулом.
не в выигрыше сферических наносекунд в вакууме, а в стабильности работы и отклика
сферических наносекунд в вакууме,
750тысяч раз
наносекунд
750тысяч раз.

Поражение засчитано. Для будущих поколений по поводу срача выше - www.linux.org.ru/forum/development/10655976?lastmod=1452495519485#comment-106...

Ыыы. Теперь ты пытаешься оправдать свою портянку. Видимо зацепило пукан. Ну ничего, дай свой адрес, я тебе вышлю огнетушитель.

«Двоичный поиск» это как-бы просто _название алгоритма_. Ну называется алгоритм так, что поделать. Но ты же не скажешь, что поиск (просто поиск) – это алгоритм? Нет, конечно же. Поиск может работать по тому или иному алгоритму(мам), но сам по себе это не алгоритм. Как и большая разница с trie. Trie – всего навсего _структура данных_ для быстрого доступа, и к поиску не имеет никакого отношения.

Что за шизофазия? В посте, нак оторый тебе указали ты же сам написал: «Скорость поиска никак не может _не зависеть_ от кол-ва записей. И обязательно нужно более детально описать процесс поиска. Скажем, если ты ищешь по точному совпадению X1, и на искомом поле существует индекс бла-бла-бла»

Но ведь индекс, который ты упоминаешь – это «всего навсего _структура данных_ для быстрого доступа», и, по твоей извращённой логике, к поиску не имеет никакого отношения, баран.

любая структура данных с O(nlogn) асимптотикой. Сбалансированное дерево, например.

O(nlogn)

O(logn), селффикс

к поиску не имеет никакого отношения, баран.

Действительно. В тарелке может быть суп, и мне ничего не запрещает говорить одновременно и о супе и о тарелке, но строго говоря – суп абсолютно независимое вещество, к тарелке отношения не имеющее, пока в ней не окажется. Так и индекс – это структура данных, а поиск – конкретное действие (не факт! что использующее индекс). Именно поэтому я сказал что «нужна конкретика». И поэтому фразу «Скорость поиска никак не может _не зависеть_ от кол-ва записей.» нужно воспринимать буквально, ибо при поиске (действии) тебе, возможно, придется искать _в записи_. Неважно в одной, или среди. Т.е. фактически ты все равно зависишь от кол-ва данных в общем смысле. Я уже сказал выше что я подразумеваю под «поиском», баран.

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

Интересно-интересно. Почему же ты не отвечаешь мне.

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

Ты что-то перепутал, я никого не звал, лалка.

Обоссать бы тебя, хотя уже обоссал, но это такое.

Обоссал ты только сам себя, я уже тебе пояснил, «хозяин». Бугага.

Интересно-интересно. Почему же ты не отвечаешь мне.

На что успеваю, на то и отвечаю, болезный.

Можно ключ разбивать на символы не по байтам, а по хексам, тогда будет

struct node_t {
    node_t *childs[16];
}

Искать будет чуть дольше, зато будет намного меньше памяти жрать.

trie стоит 1кб на каждый шаг уникального пути для ascii, если у тебя флаг хранится в указателе.

Ты либо тестил как все тестировщики на килобайте, либо использовал какой-то сжатый вариант.

У меня само дерево в файле и в оперативку подгружаются только нужные ветки. Клиентов которые одновременно будут обращаться к бд - максимум 5, строки обычно по 40 байт (в среднем). Возьмём сверхъестественный случай: клиентов 10, в каждой строке по 60 байт, получаем 60*10*1кб=600кб, по нынешним меркам - смех. И не важно на деревьях какого размера я тестировал - подгружаться будут только нужные ветки.

Ну допереть до n-ного бревна, где n длинна алфавита не такое уже и достижение.

А где ты видел чтобы я сказал, что это достижение?

У меня само дерево в файле и в оперативку подгружаются только нужные ветки. Клиентов которые одновременно будут обращаться к бд - максимум 5, строки обычно по 40 байт (в среднем). Возьмём сверхъестественный случай: клиентов 10, в каждой строке по 60 байт, получаем 60*10*1кб=600кб, по нынешним меркам - смех. И не важно на деревьях какого размера я тестировал - подгружаться будут только нужные ветки.

И? Я говорю про случаи вменяемой реализации, а не убожества. Кому интересны решения, которые встанут раком на 10финдах в секунду? Да и «подгружаются только нужные ветки» лишь в твоих фантазиях.

Можно ключ разбивать на символы не по байтам, а по хексам, тогда будет

Можно по сколько угодно.

Искать будет чуть дольше, зато будет намного меньше памяти жрать.

Чуть? Действительно - всего в 2раза дольше.

зато будет намного меньше памяти жрать.

Уменьшается нода, а вместе с нею увеличивается кол-во путей. Будет из гагабайта 250метров - толку с этого, если это в 2раза медленнее?

Я уже показал решение, которое реально «немного медленнее» и реально намного меньше памяти жрёт.

С чего это ты с «потребляет много памяти» перешел на «я не видел твой код но он неинтересное говно»? Нет аргументов - молчи в тряпочку, умней казаться будешь, а если школотролль, так профилактических бан нужен.