Здравствуйте, AndrewVK, Вы писали:
AVK>Касательно CompositeRanges тот же вопрос
По CompositeRanges — можно перенести, если устраивает, что потом могут быть блокирующие изменения (только на бинарном уровне, при перекомпиляции всё ок).
Мне сильно не нравится текущий подход с логикой, спрятанной в extension methods, но ничего лучше я пока придумать не могу.
Затык в необходимости делать перегрузки и .Contains<T>(T value), и .Contains<TRange>(TRange range) where TRange:IRange<T>
Тупо генерить все комбинации (а диапазонов у нас в итоге 4 класса) не тянет, извращаться с интерфейсами без генериков == боксинг (диапазоны структурами сделаны). В общем, сам себя в ловушку загнал
Здравствуйте, Sinix, Вы писали:
AVK>>Касательно CompositeRanges тот же вопрос S>По CompositeRanges — можно перенести, если устраивает, что потом могут быть блокирующие изменения (только на бинарном уровне, при перекомпиляции всё ок).
Перенес. Пришлось изрядно поковыряться с таргетингом.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, Sinix, Вы писали:
AVK>>Касательно CompositeRanges тот же вопрос S>По CompositeRanges — можно перенести, если устраивает, что потом могут быть блокирующие изменения (только на бинарном уровне, при перекомпиляции всё ок).
CompositeRangeInternal.cs с 40 по 72 строку — три internal метода, которые нигде не используются. Да еще и тщательно прокомментированные. Это вообще зачем?
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>CompositeRangeInternal.cs с 40 по 72 строку — три internal метода, которые нигде не используются. Да еще и тщательно прокомментированные. Это вообще зачем?
А, я их (все четыре в смысле) в хелперы хочу вытащить. Только пока не соображу, куда приткнуть с учётом того, что у нас уже есть Lower/UpperBoundary().
Здравствуйте, Lexey, Вы писали:
L>Если по существующему API SuffixTree вопросов нет, то его можно перетащить.
У меня нет (емнип, у меня было только пожелание впраралель реализовать еще и interval tree на базе наших же Ranges). Если в процессе перетаскивания появятся — напишу.
L>К DisjointSet'у, помнится, претензии были.
И? Ты их собираешься учесть или забить?
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>У меня нет (емнип, у меня было только пожелание впраралель реализовать еще и interval tree на базе наших же Ranges). Если в процессе перетаскивания появятся — напишу.
О, такой вопрос: нам нужен просто interval tree с поиском по границам с-по, или полноценный аналог CompositeRange?
Я пока не уверен, что второй вариант нам нужен, если есть доводы за — это будет отлично. Почему так:
В текущем CompositeRange поддиапазоны всегда хранятся отсортированными по левой границе, т.е. мы можем сделать простой поиск по левой границе за O(log n), но эффективного пересечения с единичным диапазоном не будет.
Для меня это неактуально абсолютно, т.к.
1. В наших сценариях в диапазоне никогда не было больше нескольких сотен поддиапазонов, в большинстве случаев — пара десятков значений.
2. Почти во всех операциях оба операнда — составные диапазоны, т.е. всё равно скатываемся к O(M+N).
Если есть реальные сценарии для универсального класса диапазонов поверх interval tree — отлично, если нет — можем пока отложить.
Здравствуйте, Lexey, Вы писали:
L>Если по существующему API SuffixTree вопросов нет, то его можно перетащить.
Вопросы по SuffixTree
1) Допиши комментарий к параметрам BuildFor.
2) Названия методов FindBranchingPoint и CreatePendingLink как то не очень коррелируют с void
3) В FindBranch наверное лучше поменять Tuple на ValueTuple или специализированную структурку
4) Насколько необходим implicit operator string(Suffix suffix)?
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, AndrewVK, Вы писали:
S>>О, такой вопрос: нам нужен просто interval tree с поиском по границам с-по, или полноценный аналог CompositeRange? AVK>ХЗ. Лично мне, наверное, хватило бы простого, а как остальным не знаю.
Ну тогда я предлагаю сделать (по крайней мере пока) банальный Interval tree без всего функционала CompositeRange, просто поверх Range<T>.
Centered interval tree не будет работать для произвольных типов данных, к примеру у диапазона "от одного исключительно до двух исключительно, тип данных — int" вообще нет представимых как int значений. Остаётся только augmented-вариант, как понимаю.
AVK>Ну, лично мне нужно именно "which of these intervals contains a given point".
Дополнительный момент — неплохо было бы иметь какую то балансировку для неравномерного распределения интервалов. Но как это алгоритмически обеспечить — отдельный большой вопрос.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, AndrewVK, Вы писали:
S>>И да, нам именно interval trees нужны?
AVK>Ну, лично мне нужно именно "which of these intervals contains a given point".
Угу, сделаю для CompositeRange, но там по сути O(n) будет. Отсечь "интервалы начинаются после заданной точки" легко, чтоб найти которые заканчиваются до — надо все оставшиеся перебирать.
Как вариант можем рядышком хранить массив "правая граница диапазона; индекс диапазона в основном массиве" и делать бинарный поиск ещё и по нему (сортировать по границе, понятно). По эффективности будет всяко лучше, чем btree на ссылках.
Поиск получается 2*log(n), любые операции — что-то в районе (m+n)*log(n), если правильно прикинул.
Здравствуйте, Sinix, Вы писали:
S>Как вариант можем рядышком хранить массив "правая граница диапазона; индекс диапазона в основном массиве" и делать бинарный поиск ещё и по нему (сортировать по границе, понятно). По эффективности будет всяко лучше, чем btree на ссылках. S>Поиск получается 2*log(n), любые операции — что-то в районе (m+n)*log(n), если правильно прикинул.
Выбор подходящего алгоритма это отдельный большой вопрос и он сильно зависит от данных. На малых количествах интервалов (прикидочно 5-10) тупой перебор сортированного массива будет быстрее всего. Если диапазон на целых числах и суммарный диапазон невелик, но диапазонов относительно много, то быстрее всего будет простейшая таблица. Если суммарный диапазон большой, а диапазонов мало, то неплохо будет работать хеш-индекс. А вот если диапазонов много и суммарный диапазон большой, тот тут будет рулить interval tree.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>И? Ты их собираешься учесть или забить?
Они были из разряда: "нет реальных юз-кейсов". К сожалению, тут я ничего сделать пока не могу, ибо мне хватало того, что есть, а сценариев, по которым можно было бы придумать другое API, нет.
Здравствуйте, AndrewVK, Вы писали:
AVK>Вопросы по SuffixTree AVK>1) Допиши комментарий к параметрам BuildFor.
AVK>2) Названия методов FindBranchingPoint и CreatePendingLink как то не очень коррелируют с void
Есть предложения по другим названиям?
AVK>3) В FindBranch наверное лучше поменять Tuple на ValueTuple или специализированную структурку
Вроде я менял Tuple на ValueTuple везде, где видел в этом смысл. Но мог и забыть.
AVK>4) Насколько необходим implicit operator string(Suffix suffix)?
Не необходим. Но мне подумалось, что он может быть удобен, поскольку чаще всего пользователю будет нужна именно строка суффикса, а не его полное представление. Если думаешь, что лучше его убрать, то уберу.
Здравствуйте, Lexey, Вы писали:
AVK>>2) Названия методов FindBranchingPoint и CreatePendingLink как то не очень коррелируют с void L>Есть предложения по другим названиям?
Для этого надо вникать в сам алгоритмы. А я чисто внешне, по возникшим WTF при просмотре кода.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
