Pull to refresh
  • by relevance
  • by date
  • by rating

Поиск анаграмм и сабанаграмм во всех словах языка

Entertaining tasksProgrammingJavaAlgorithms
Решение задач с анаграммами натолкнуло на мысль:
Сколько останется слов, если удалить все анаграммы и сабанграммы из словаря русского языка

В найденном словаре больше 1,5 млн слов в различных формах

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

Но есть ли решение получше?
Читать дальше →
Total votes 13: ↑13 and ↓0 +13
Views4.9K
Comments 6

Радужные раскраски — лучшие друзья математиков

MathematicsPopular science
Translation

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



Цветовое кодирование латинского квадрата и его графа может многое о них рассказать

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

Гипотеза Рингеля – это задача из области комбинаторики, связанная с построением графов – точек (вершин), соединённых линиями (рёбрами). Она предсказывает наличие особого взаимоотношения между крупными графами определённого типа с 2n + 1 вершиной и пропорционально меньшими графами с n + 1 вершиной.
Читать дальше →
Total votes 9: ↑8 and ↓1 +7
Views2K
Comments 1

Текстовый индекс по котировкам в памяти на Go

High performanceSearch enginesProgrammingAlgorithmsGo
Translation

Недавно понадобилось реализовать поиск по началу строки, по сути WHERE name LIKE 'начало%'. Это был поиск по названию биржевых символов (AAPL, AMZN, EUR/USD и пр.). Хотелось, чтобы поиск работал быстро, и не нагружал лишний раз БД. В итоге пришел к реализации поиска по дереву в памяти, об этом и расскажу.

Читать далее
Total votes 8: ↑5 and ↓3 +2
Views2.7K
Comments 16

Почему единственный вид деревьев не победил все остальные?

MathematicsPopular scienceEcology
Translation

«Лес красив, дремуч, высок», — писал Роберт Фрост. Этот ямб вспоминается мне каждый раз, когда я начинаю путь по расположенной недалеко от моего дома лесной тропе. Тропу назвали в честь Фроста, который провёл несколько лет в этой части Массачусетса, обучая мальчиков в блейзерах с медными пуговицами из Амхерстского колледжа. Прогуливался ли поэт среди именно этих деревьев? Такое возможно, хотя тогда, век назад, они были ещё молодняком. Как бы то ни было, если он и останавливался возле этого леса, то ненадолго, ведь «ждут меня сегодня в срок, а до ночлега путь далек».

Когда я шёл тропой Фроста, она привела меня к непримечательной лужайке в лесистой местности Северо-запада, зажатой между шоссе, домами и городской свалкой. Она не была ни дремучей, ни высокой, и ощущение близости людей никогда не пропадало. Это не был девственный лес, однако он был достаточно лесистым не только для того, чтобы вспомнить рифмы популярных поэтов, но и задаться сложными вопросами о деревьях и лесах — вопросами, которые волновали меня уже многие годы. Почему деревья такие высокие? Почему они не становятся выше? Почему их листья имеют такое разнообразие форм и размеров? Почему деревья являются деревьями (в том смысле, который используется в теории графов), а не имеют какую-то другую структуру? И был ещё один вопрос, который бы я хотел обсудить сегодня:

Сегодняшний вопрос: почему в смешанном лесу виды деревьев остаются смешанными?
Читать дальше →
Total votes 127: ↑125 and ↓2 +123
Views49.6K
Comments 120

Nested Sets для Javascript

JavaScriptNode.JS
Sandbox
На любом современном сайте (да и на сайтах постарше) встречаются вложенные структуры, иерархия объектов, деревья. Самый распространенный пример — каталог.

Сегодня множество проектов разрабатывается с использованием Javascript. Как же хранить древовидные структцры в этом случае? Об этом и хотелось бы поговорить.
Читать дальше →
Total votes 16: ↑10 and ↓6 +4
Views3.4K
Comments 17

Система управления иерархическими древовидными комментариями для Laravel

PHPLaravel

Пакет для фреймворка Laravel, который позволяет организовать управление древовидными комментариями. Используется симбиоз двух методов хранения иерархических структур — «Closure Table» и «Adjacency List».

Совместное применение методов «Closure Table» и «Adjacency List» позволяет: Минимизировать количество запросов к базе данных. Для извлечения ветки комментариев достаточно одного запроса, обеспечить высокую производительность, гарантировать целостность данных иерархи, работать с древовидными структурами без рекурсивных запросов.

Читать далее
Total votes 7: ↑7 and ↓0 +7
Views2.7K
Comments 9

Как подружить ltree и Laravel

Open sourcePHPPostgreSQLGitHubLaravel
Tutorial

Вообще Postgres очень известен и о расширении ltree написано, если немного, то достаточное кол-во публикаций, в том числе и на Хабре тоже, да и сообщество Laravel довольно обширное.

Но как ни странно, я обнаружил полное отсутствие каких-либо библиотек для работы с расширением ltree (от PostgreSQL) под Laravel на GitHub.

Есть некоторые попытки для Yii2, также есть наработки для Symfony (по моему bundle для 2-й, из коробки не работает), и на этом, пожалуй, все.

Это очень грустно, что и послужило поводом написания данной статьи, как наверное и от части, желание поделиться с вами своим опытом работы с древовидными справочниками в Laravel, т.е. как мы работаем с ltree в своих проектах, собственно, почему в итоге мы выделили эти компоненты в GitHub в общий доступ.

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

Погнали!
Total votes 6: ↑6 and ↓0 +6
Views2.3K
Comments 1