Поиск в текстовом массиве. Быстрый алгоритм. , Идеи, решения, алгортимы

[FasterHarder]

ищется по условии задачи ПОЛНОЕ соответствие строки или может быть ее часть?
т е если дана строка: "Привет МИР! Солнце светит, погода прекрасна"
то может ли быть поиск фразы "Солнце светит" или "да" или вся фраза целиком с точностью до символа?

[Vlasssov]

Цитата MBo @ 06.10.10, 11:57

>Что быстрее обработать - текстовую переменную, или массив данных?
Что значит - обработать?

Во многих языках программирования поиск фрагмента в сроке реализован в виде функций. Вот в VisualBasic
instr
http://msdn.microsoft.com/ru-ru/library/8460tsh1%28VS.90%29.aspx
То есть, если добавлять в строковую переменную очередной найденный фрагмент, и потом осуществлять с помощью стандартной функции поиска из любого языка (ну мы не берем случай ассемблера), то не будет ли быстрее, просто осуществить поиск с помощью данной функции?

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

Цитата Akina @ 06.10.10, 12:12

В СОРТИРОВАННЫЙ массив с СОХРАНЕНИЕМ сортировки - да. Иначе - с какой бы стати? пихай в конец, и всё.

Akina, вы говорите загадками. То вы хихикаете, про бинарный поиск в НЕОТСОРТИРОВАННОМ массиве,

Цитата Akina @ 05.10.10, 19:29

Цитата (Vlasssov @ 5.10.10, 13:34)
Интересно ак как осуществлять бинарный поиск на неотсортированном массиве?

Этого я не знаю...

тот начинаете хихикать, про

Цитата Akina @ 04.10.10, 17:39

Подготовительные операции к реализации твоей идеи гарантированно сожрут любой выигрыш от её гениальности.

При этом пишите:

Цитата Akina @ 06.10.10, 04:41

Судя по ответам, все прочитали внимательно и не пропустили информацию о добавлении

Еще раз вам расскажу про задачу. Может что я не так написал. Есть неупорядоченный никаким образом массив текстовых срок. Например:
$avArray[0] = "JPM"
$avArray[1] = "Holger"
$avArray[2] = "Tylo"
$avArray[3] = "Larry"
$avArray[4] = "Jeremy"
$avArray[5] = "Tylo"
$avArray[6] = "Cyberslug"
$avArray[7] = "Nutster"
$avArray[8] = "Holger"
$avArray[9] = "Tylo"

Сформированный абсолютно "от балды. " При этом в нем есть , как можно заметить, повторяющиеся элементы. Так вот надо составить массив

$avArray[0] = "JPM"
$avArray[1] = "Holger"
$avArray[2] = "Tylo"
$avArray[3] = "Larry"
$avArray[4] = "Jeremy"
$avArray[5] = "Cyberslug"
$avArray[6] = "Nutster"

С уникальными именами. Очень похоже на SQL-запрос о повторяющихся записях. Полученный на выходе массив не должен быть упорядочен. Так понятней? Причем с каждым поиском массив будет увеличиваться. Естественно, что главной трудоемкой задачей будет проверка на уникальность.

Добавлено 07.10.10, 05:12

Цитата FasterHarder @ 06.10.10, 13:24

ищется по условии задачи ПОЛНОЕ соответствие строки или может быть ее часть?
т е если дана строка: "Привет МИР! Солнце светит, погода прекрасна"
то может ли быть поиск фразы "Солнце светит" или "да" или вся фраза целиком с точностью до символа?

Вся фраза целиком с точностью до символа. Потому что по сути это набор из уникальных имен, в приведенном примере, это можно проиллюстрировать вот так:
Текстовая строка "JPM Holger Tylo Larry Jeremy Cyberslug Nutster"
Ну и соответственно поиск, например "JPM".

[Akina]

Цитата Vlasssov @ 07.10.10, 05:08

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

instr - функция небыстрая, кстати...

Цитата Vlasssov @ 07.10.10, 05:08

Akina, вы говорите загадками. То вы хихикаете, про бинарный поиск в НЕОТСОРТИРОВАННОМ массиве,

я?

Цитата Vlasssov @ 07.10.10, 05:08

Еще раз вам расскажу про задачу.
[skipped]
Полученный на выходе массив не должен быть упорядочен. Так понятней? Причем с каждым поиском массив будет увеличиваться. Естественно, что главной трудоемкой задачей будет проверка на уникальность.

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

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

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

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

[MBo]

Vlasssov
>то не будет ли быстрее, просто осуществить поиск с помощью данной функции?

В общем - поиск по дереву быстрее.


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

Во-первых, по упорядоченному массиву легко строится идеально сбалансированное дерево (средний элемент взять за корень, повторить для левой и правой половины и т.д.). Но реальный смысл это имеет только для статического набора данных.

Во-вторых, на практике в большинстве случаев используются сбалансированные (самобалансирующиеся) деревья - два вида я уже упоминал,

[Vlasssov]

Цитата Akina @ 07.10.10, 05:29

Наибольшую проблему представляет процесс физического удаления дублей элементов.

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

Цитата MBo @ 07.10.10, 06:00

Во-первых, по упорядоченному массиву легко строится идеально сбалансированное дерево (средний элемент взять за корень, повторить для левой и правой половины и т.д.). Но реальный смысл это имеет только для статического набора данных.

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

Цитата MBo @ 07.10.10, 06:00

В общем - поиск по дереву быстрее.

Поверим на слово...

Цитата Akina @ 07.10.10, 05:29

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

Хм.. А создание элемента коллекции как по расходу машинных ресурсов как соотносится с массивом? Просто массив можно создать с избыточной размерностью. В моем случае (реальная задача) количество элементов в любом случае не будет превышать 30000.

Сообщение отредактировано: Vlasssov - 07.10.10, 07:07

[Akina]

Цитата Vlasssov @ 07.10.10, 07:06

создание элемента коллекции как по расходу машинных ресурсов как соотносится с массивом?

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

Цитата Vlasssov @ 07.10.10, 07:06

массив можно создать с избыточной размерностью

А коллекции это вообще по барабану.

Добавлено 07.10.10, 07:43

Цитата Vlasssov @ 07.10.10, 07:06

это я не оговорил в условии

Так... чего ещё мы не знаем?

[Vlasssov]

Цитата Akina @ 07.10.10, 07:43

Так... чего ещё мы не знаем?

Ну вообще то речь изначально не об исключении дублей, а о поиске...

[Akina]

Ок, забиваем на дубли. При построении дерева и в дальнейшем при поиске по барабану, есть там дубли или нет.

[Vlasssov]

Цитата Akina @ 07.10.10, 07:54

Ок, забиваем на дубли. При построении дерева и в дальнейшем при поиске по барабану, есть там дубли или нет.

Да ладно!!! По скорости обработки - есть.

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


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

Сообщение отредактировано: Vlasssov - 16.10.10, 02:26

[05772]

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

[Bug Hunter]

Цитата Vlasssov @ 16.10.10, 02:17

Тут еще одна идея в голову пришла..

<бла-бла-бла>

А можно еще нарисовать на стене оранжевый круг...

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

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

Цитата Vlasssov @ 07.10.10, 07:06

А создание элемента коллекции как по расходу машинных ресурсов как соотносится с массивом?

От того, что сортировка запихнута в нутро коллекции, быстрее оно работать не станет. Тебе надо совсем от сортировок уйти.