Войти
ФлеймФорумПрограммирование

Задачка по алгоритмам (3 стр)

Страницы: 1 2 3 4 Следующая »
#30
10:56, 30 ноя. 2018

}:+()___ [Smile]
Это значит, что ты должен отсекать половину на каждой итерации поиска.
Но тебе же не нужно чтобы коллекция была читаема удобно для человека? Ну сделай Trie какое-нибудь. Или SuffixArray/SuffixTrie.


#31
11:00, 30 ноя. 2018

*Lain*
> Читая твой пост подумалось что смайлу надо сжатие в реалтайме. Что-то какая-то
> божественная коллекция
Сдаётся мне, она не особо будет сжимать, а скорее наоборот.
И по сравнению с обычными строками ускорение будет лишь в теории, ибо такой логарифм будет во много раз медленнее оотэнного обхода соседних байтов по линеечке. По крайней мере, если задача именно в таком виде.

#32
11:21, 30 ноя. 2018

=A=L=X=
> Попытаться сделать...
Чёт по моему херня какая-то получится в результате.

#33
13:02, 30 ноя. 2018

Dexus
> Наверное, имеет смысл сразу закладываться в слоговые фрагменты, а не только отдельные символы.
Не, понятно, что в финальной версии строки меньше некоторого размера (назовем его размер блока) будут храниться по месту, как обычные строки.
И только по превышении размера блока начинается всякая магия с деревьями и дедупликацией.

Однобуквенные ноды будут просто проще, чем блоковые, придумывать алгоритм удобнее будет.

#34
13:51, 30 ноя. 2018

}:+()___ [Smile]
>> Сравнение за O(log N) тупо поиском в этом списке.
> Каждая операция сравнения будет недешевой.
В таком виде - вроде нет. "Список" тупо хранит непрозрачные хендлы (с implementation-defined смыслом), по которым ты, собственно, свои функции и вызываешь. Условно - твои String из #18.
Каждая строчка знает свой узел в "списке" (ну да, оно дерево). Так что сравнения - тупо подняться от обоих до корня.
Тут проблема в другом - операции substring/concat тоже создают новый хендл, так что при этих операциях нужно как-то быстро обновить "список" (быстрее, чем при создании строки "снаружи"). Что мне непонятно, как.
Так что облом.

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

#35
15:27, 30 ноя. 2018

}:+()___ [Smile]
> у вот вариант с кодом — надо написать класс (менеджер строк будем считать
> глобальным объектом):
вижу что почти для всех методов одинаковые требования, но при использовании скорее всего нагрузка на каждый метод будет не одинаковая => задача слишком теоретическая => ловить тут похоже нечего.

можно хранить всю строку в size_t, если какая-то конкретная строка не влезет, то просить пересобрать прогу на системе с таким size_t чтобы она влезала :)

added:
ещё можно попытаться сделать N реализаций и конвертеры между ними. но пользовательское приложение должно будет из-за нашей системы иметь в N раз больше реализаций, и так же иметь конвертеры между ними. затем делаем фасад для всей системы который будет предсказывать что вот сейчас будет большая нагрузка на такую-то пачку методов и перекачивать/конвертить состояние всей системы из одной реализации в другую.

#36
15:51, 30 ноя. 2018

А что будет, если все конечные (после ряда преобразований) строки в коллекции будут конкатенациями однобуквенных субстрингов из исходных строк? Мне кажется, что ГАРАНТИРОВАННОЕ ограничение сложности вообще невозможно получить, а только с допущениями.

#37
16:06, 30 ноя. 2018

FordPerfect
> Тут проблема в другом - операции substring/concat тоже создают новый хендл, так что при этих операциях нужно как-то быстро обновить "список"
Да, я именно это имел в виду: сравнения при добавлении новой строки в список.

Dmitry_Milk
> А что будет, если все конечные (после ряда преобразований) строки в коллекции будут конкатенациями однобуквенных субстрингов из исходных строк?
Это, кстати, и будет основным режимом работы: большинство строк будут создаваться инкрементально из мелких кусочков.

> Мне кажется, что ГАРАНТИРОВАННОЕ ограничение сложности вообще невозможно получить, а только с допущениями.
Лично я пока не вижу принципиальной невозможности, но доказательство отсутствия решения — это тоже решение задачи.

#38
16:12, 30 ноя. 2018

}:+()___ [Smile]
> а операция добавления в коллекцию строки длиной L — за O(LlogS)
Больше всего вопросов к этой строчке. Фактически, добавление это L раз поискать.....
И как это будет работать, если в контейнере 1 строка. Как её разбивать на log???

#39
17:32, 30 ноя. 2018

Чорд, а мы были так близки к созданию ИИ...

#40
18:05, 30 ноя. 2018

}:+()___ [Smile]
Мысль: можем ли мы, не теряя ассимптотической сложности по сравнению со сбалансированным деревом, иметь каноническое представление? Т. е. строка длины больше 1 это всегда конкатенация ceil(L/2) и floor(L/2). Тогда эти подстроки можно считать буквами в алфавите переменной длины, и, подозреваю, можно обеспечить их уникальность.

#41
18:59, 30 ноя. 2018

Можно вычислить хеши для кaждого пoложения в строке фиксированного значения, напримеp начиная от длинны oxff, и их степений,  получится NLogN для хранения.
При сравнении сравниваем сначала хэши, если совпадают сравниваем значения.

#42
22:03, 30 ноя. 2018

256-арное дерево предлагали уже?

Кстати, из формулировки непонятно, как должны идентифицироваться строки в коллекции. То есть, чем должно определяться, над какой именно из строк в коллекции требуется произвести какую-либо операцию? Если считать, что сам контент строки и есть ее идентификатор - то вроде 256-арное дерево пойдет.

#43
22:07, 30 ноя. 2018

Dmitry_Milk
> 256-арное дерево предлагали уже?
Да:
> префиксное дерево

#44
22:37, 30 ноя. 2018

}:+()___ [Smile]
> Надо попробовать придумать дедупликацию
Ну если тебе ropes подходят, и подходит амартизированное время, то мне кажется достаточно просто к каждому сегменту добавить и хранить хеш. И определить так же операции над хешем. Тогда получишь константное время на конкатенацию, удаление из коллекции и добавление в коллекцию. Но в случае коллизий понятное дело будет O(L) операций.
Единственное, что не вписывается сюда пока, так это лексикографическое сравнение и выделение подстроки.

Страницы: 1 2 3 4 Следующая »
ФлеймФорумПрограммирование

Тема в архиве.