Word Tables

Word Tables

А как вообще хранят таблицы слов,
чтобы быстро искать/вставлять/удалять ?

Ну есть hash table (HashMap) и сбалансированные
бинарные деревья (TreeMap). Есть еще trie.

А еще ?

Миша

Re: Word Tables

Юpa Шaлaк <jupastor@gmail.com> wrote:


А вот это вот - совершенно неочевидно.
Специализированное решение - в большинстве случаев
эффективнее общечеловеческого.




Если все приложение заключается в поддержке вот этого единственного
специализированного решения - безусловно. Вот, например, Гугл.


Так эпизодическое использование без эффективности - это точно то,
о чём Миша спрашивал ?
И даже в таком странном случае я бы еще сто раз подумал,
прежде чем вводить в систему новый элемент.


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


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




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


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




Я ничего не имею против того, чтобы Вы эти теории продавали АТТ.
Но мы-то здесь все свои, нет?


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





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

воистину это всего-лишь здравый смысл.


Не, это eine Colonne marschiert или как там оно было.




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


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

---
Const

Re: Word Tables

"Const" <ocra@optonline.net> wrote in message
news:fu6lmi$les$1@mamba.crocodile.org...


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


А расскажите!


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


Вообще конечно поражает.

Почему люди стремятся все делать по шаблону,
когда можно немного подумать ?

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

Миша

Re: Word Tables

Mikhail Kimmelman <mikhail.kimmelman@gmail.com> wrote:

"senatov" <jakov-senatov@t-online.de> wrote in message
news:fu5u0i$oln$01$1@news.t-online.com...




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




А какую базу данных использует в юниксе комманда spell ?


Вот это, Миша, очень хороший вопрос.
Но еще более правильным является вопрос к заказчику
"А вы уверены, что это вам вообще нужно ?
А давайте обсудим зачем."
Если в команде имеется человек с достаточным весом и мозгом,
который задает такие вопросы, то на самом деле 99%
подобных требований как-то сами собой рассасываются.


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


Чрезмерно увлекаться-то тоже не надо.

---
Const

Re: Word Tables

"Const" <ocra@optonline.net> wrote in message
news:fu6m7a$les$3@mamba.crocodile.org...



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


Чрезмерно увлекаться-то тоже не надо.


Думаю, в Израиле это из армии идет.

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

Миша

Re: Word Tables

On Apr 16, 11:30 pm, "Mikhail Kimmelman" <mikhail.kimmel...@gmail.com>
wrote:




А как вообще хранят таблицы слов,
чтобы быстро искать/вставлять/удалять ?
Ну есть hash table (HashMap) и сбалансированные
бинарные деревья (TreeMap). Есть еще trie.
А еще ?

Да как кому удобно, так и хранят (начиная

< от линейных списков на cons cells -
Это как ?


Как в Лиспе. Народ от них тащился, когда была мода на "параллельное
программирование" - они очень дёшево клонируются.

С тех пор, конечно, появились аналогичные (дёшево клонирующиеся)
структуры и с более эффективным поиском. Основные идеи, например, вот
здесь:

http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Но это, повторюсь, под весьма специфичные задачи.

Kit.

Re: Word Tables

Mikhail Kimmelman wrote:



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

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

Э-э-э. Ты что, не понимаешь разницы между динамической
DB где надо, как ты сказал "быстро искать/вставлять/удалять"
и низкопроизводительной, статической, read-only, ввв 99%
cлучаев только на выдачу по ключу?

--
Привет. Иаков
--- -- -- -- -- -- --- -- ---
ICQ № 24392270 / Skype:senatov

Re: Word Tables

Mikhail Kimmelman wrote:



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

ты уже вроде на той неделе изобрёл
по ходу идею CMS, теперь, как я понял подбираешься к открытию
relational DB и 10 принципам Кодда.

:) :)



--
Привет. Иаков
--- -- -- -- -- -- --- -- ---
ICQ № 24392270 / Skype:senatov

Re: Word Tables

??>> ещё есть какой-то DAWG: A directed acyclic word graph (DAWG) is a data
??>> structure in computer science similar to a trie but much more
??>> space efficient.


Интересно. А можно своими словами ?


могу ещё чужих написать :)

A DAWG is defined as a trie where isomorphic subtrees are identified, thus
producing an acyclic directed graph instead of a tree structure.
The primary difference between DAWG and trie is the elimination of suffix
redundancy in storing strings.

http://en.wikipedia.org/wiki/D... 


Re: Word Tables

Mikhail Kimmelman wrote:

"Юpa Шaлaк" <jupastor@gmail.com> wrote in message
news:FxxNj.6262$nT1.3974@trndny09...


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


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


Конечно же свою. Если Вы пишете спеллчекер - так и скажите. :-)

Re: Word Tables

Const wrote:

Юpa Шaлaк <jupastor@gmail.com> wrote:


А вот это вот - совершенно неочевидно.
Специализированное решение - в большинстве случаев
эффективнее общечеловеческого.




Если все приложение заключается в поддержке вот этого единственного
специализированного решения - безусловно. Вот, например, Гугл.


Так эпизодическое использование без эффективности - это точно то,
о чём Миша спрашивал ?
И даже в таком странном случае я бы еще сто раз подумал,
прежде чем вводить в систему новый элемент.


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



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


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


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





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


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




Я ничего не имею против того, чтобы Вы эти теории продавали АТТ.
Но мы-то здесь все свои, нет?


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


Так база АТТ и есть тот специальный случай. Как и база Гугла.
Я [почти] не иронизировал по поводу "продать АТТ".


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


Ну Вы же знаете, что бесплатный и естественный сыр бывает только в
мышеловках. Значит чем-то пожертвовано в рамках естественных
допущений. А Оракл этим жертвовать не может. Потому что наверняка
напорется на клиентов, которые уткнутся в эту проблему.

Re: Word Tables

"Nikita V. Belenki" <fido7@kits.net> wrote in message
news:2b9cd131-9dcb-4510-ab29-bef59f8ac682@m71g2000hse.googlegroups.com...


Как в Лиспе. Народ от них тащился, когда была мода на "параллельное
программирование" - они очень дёшево клонируются.

С тех пор, конечно, появились аналогичные (дёшево клонирующиеся)
структуры и с более эффективным поиском. Основные идеи, например, вот
здесь:

http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Но это, повторюсь, под весьма специфичные задачи.


Спасибо.

Миша

Re: Word Tables

"senatov" <jakov-senatov@t-online.de> wrote in message
news:fu72b3$sp0$03$1@news.t-online.com...



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

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


А что это за таблицы ?


Э-э-э. Ты что, не понимаешь разницы между динамической
DB где надо, как ты сказал "быстро искать/вставлять/удалять"
и низкопроизводительной, статической, read-only, ввв 99%
cлучаев только на выдачу по ключу?


Я ж не сказал, что все изменения в таблице должны быть
persistent. И кто Вам сказало про низкую производительность ?

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

Ну да, не удаляет ничего.

Но можно привестипример программы, которой требуются
и удаления тоже. Компилятор, скажем, который хранит таблицы
символов и т.д. Вроде без базы данных обходится.

Миша


Re: Word Tables

Mikhail Kimmelman wrote:



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


А что это за таблицы ?

типа замшелого dBase.
Текстовые, плоские, индексируются , файловый интерфейс.
Для автономной, одиночной аппликухи - то что надо.

<рассуждения о том, каким должен быть настоящий велосипед поскипаны>
--
Привет. Иаков
--- -- -- -- -- -- --- -- ---
ICQ № 24392270 / Skype:senatov

Re: Word Tables

"senatov" <jakov-senatov@t-online.de> wrote in message
news:fu864v$fip$01$1@news.t-online.com...




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


А что это за таблицы ?

типа замшелого dBase.
Текстовые, плоские, индексируются , файловый интерфейс.
Для автономной, одиночной аппликухи - то что надо.


А чем это лучше чем просто один единственный
текстовый файл со словами ?

Миша

Re: Word Tables

"Юpa Шaлaк" <jupastor@gmail.com> wrote:



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




Традиционную базу можно заточить под работу с чем угодно. Да, будет


Не-а.
Покажите, каким именно образом Вы будете затачивать SQL Server
на работу с падежами в русском языке.


overhead,
но скорость разработки и относительная простота поддержки обычно
перевешивают.


Например, в off-the-shelf standalone продукте.
Да и в любом другом - простота поддержки, вместе
с дешевизной - ну прямо зашкаливают.
Купить базу за кучу бабок и платить админам.



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




Ну Вы же знаете, что бесплатный и естественный сыр бывает только в
мышеловках. Значит чем-то пожертвовано в рамках естественных
допущений. А Оракл этим жертвовать не может. Потому что наверняка


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

А знаете, сколько человек написало и поддерживает ?
Два.

---
Const

Re: Word Tables

"Const" <ocra@optonline.net> wrote in message
news:fu8ag8$293j$4@mamba.crocodile.org...



Традиционную базу можно заточить под работу с чем угодно. Да, будет


Не-а.
Покажите, каким именно образом Вы будете затачивать SQL Server
на работу с падежами в русском языке.



Ну, примерно так:

CREATE TABLE RussianCases
(
FormId int,
Nominative varchar(50),
Genitive varchar(50),
Dative varchar(50),
Accusative varchar(50),
Instrumental varchar(50),
Prepositional varchar(50)
)

CREATE TABLE RussianNouns
(
WordId int,
SingularFormId int,
PluralFormId int
)

CREATE TABLE RussianAdjectives
(
WordId int,
SingularMasculineFormId int,
SingularFeminineFormId int,
SingularNeuterFormId int,
PluralFormId int
)

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

Иван

Re: Word Tables

Const wrote:

"Юpa Шaлaк" <jupastor@gmail.com> wrote:



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




Традиционную базу можно заточить под работу с чем угодно. Да, будет


Не-а.
Покажите, каким именно образом Вы будете затачивать SQL Server
на работу с падежами в русском языке.


Вот там русский молодец :-) Иван Кривяков постарался.



overhead,
но скорость разработки и относительная простота поддержки обычно
перевешивают.


Например, в off-the-shelf standalone продукте.
Да и в любом другом - простота поддержки, вместе
с дешевизной - ну прямо зашкаливают.
Купить базу за кучу бабок и платить админам.


Для подавляющего большинства случаев это - выгоднее.




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




Ну Вы же знаете, что бесплатный и естественный сыр бывает только в
мышеловках. Значит чем-то пожертвовано в рамках естественных
допущений. А Оракл этим жертвовать не может. Потому что наверняка


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

А знаете, сколько человек написало и поддерживает ?
Два.


А что случится, если они уволятся?
Я вообще не понимаю, о чем мы спорим? Что можно сотворить уникальное
решение, которое будет бить по производительности коробочный софт?
Я как бы не спорю...

Re: Word Tables

Mikhail Kimmelman wrote:

"Const" <ocra@optonline.net> wrote in message
news:fu6lmi$les$1@mamba.crocodile.org...


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


А расскажите!


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

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



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


Вообще конечно поражает.

Почему люди стремятся все делать по шаблону,
когда можно немного подумать ?


Потому что у них мозга нет.


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


А им думать нечем. Они один раз зазубрили - и все.

-СБ

Re: Word Tables

Юpa Шaлaк wrote:

Const wrote:

Юpa Шaлaк <jupastor@gmail.com> wrote:




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


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


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


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



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


Ну Вы же знаете, что бесплатный и естественный сыр бывает только в
мышеловках. Значит чем-то пожертвовано в рамках естественных
допущений. А Оракл этим жертвовать не может. Потому что наверняка
напорется на клиентов, которые уткнутся в эту проблему.


MySQL может. В нем можно даже в одной и той же базе для разных
таблиц использовать разные движки.

-СБ

Re: Word Tables

Mikhail Kimmelman wrote:

"senatov" <jakov-senatov@t-online.de> wrote in message
news:fu5u0i$oln$01$1@news.t-online.com...


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


А какую базу данных использует в юниксе комманда spell ?


Я не удивлюсь, если окажется, что какую-нибудь Berkeley DB. То есть,
эти, забыл слово, индексно-чевотошные файлы.



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


Ух ты. А чем по-Вашему, отличается Сортировка в Лучших Кубиках
к примеру от обычной ?


Я однажды заменил qsort() на написанную вручную пузырьковую сортировку,
и вся программа от этого ускорилась на 20%.

-СБ