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

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

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

Suslik
> а, я, кажется, понял. если тебе нужно просто получить объект "конкатенация строк i и j", то это тоже всегда можно сделать хоть за O(1).
Именно. Вот только потом с полученным объектом тоже надо делать весь набор операций.

> как часто ты захочешь resolve'ить объекты из своей структуры данных в именно строки и за какую сложность.
Мне не для оптимизации надо, мне надо гарантировать именно оценку сверху на каждую операцию.
Т. е. чтобы не было патологических случаев, когда хитрый набор операций вызывает тормоза.
В принципе, мне сойдет даже амортизированный логарифм, но только тоже по произвольному набору операций.

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

FordPerfect
> https://en.wikipedia.org/wiki/Rope_%28data_structure%29 всё вроде ок, кроме сравнения. Гм.
В принципе, сравнение не так критично, однако, хотя бы, проверку на равенство хотелось бы иметь.
Еще там с удалением проблемы будут, непонятно, получится ли хитрым аллокатором их разрулить.

> Сравнение за O(log N) тупо поиском в этом списке.
Каждая операция сравнения будет недешевой.

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


#16
5:51, 30 ноя. 2018

}:+()___ [Smile]

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

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

#17
6:05, 30 ноя. 2018

=A=L=X=
как я понял, он хочет свести задачу к дереву, в листьях которого хранятся только символы алфавита и далее все строки(ветки) составляются из них как из подстрок. каждый элемент дерева считается отдельным объектом и над ним подразумеваются операции, которые производятся над любой самостоятельной строкой.

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

#18
6:06, 30 ноя. 2018

=A=L=X=
> Ты очень мутно описал задачу, в результате действительно ничерта непонятно.
Ну вот вариант с кодом — надо написать класс (менеджер строк будем считать глобальным объектом):

class String
{
    // ...

public:
    String(const char *str, size_t len);            // O(len*log(S))
    ~String();                                      // O(log(S))

    size_t length() const;                          // O(log(S))
    char operator [] (size_t pos) const;            // O(log(S))

    String operator + (const String &str) const;    // O(log(S))
    String substr(size_t start, size_t len) const;  // O(log(S))

    bool operator == (const String &str) const;     // O(log(S))
    bool operator < (const String &str) const;      // O(log(S))
    // остальные варианты сравнений
};

Suslik
> мне кажется, для реально применимого в жизни алгоритма это выльется в сказочный оверхед на хранение самого дерева и в листях нужно хранить конечного размера строки.
Это то да, но для начала хочется определить принципиальную возможность, а только потом заниматься оптимизацией.

#19
6:16, 30 ноя. 2018

Suslik
> мне кажется, для реально применимого в жизни алгоритма это выльется в сказочный оверхед на хранение самого дерева и в листях нужно хранить конечного размера строки.
Этo же равносильно сжатию, где адрес строки кодируется последовательностью содержимого…
Тогда строки хранить в памяти и не нужно.

#20
6:16, 30 ноя. 2018

}:+()___ [Smile]
> Ну вот вариант с кодом

А ну то есть просто строка нужна сверхбыстрая по обозначенным операциям.
Тогда насчёт O(log(S)) невыполнимо - нахождение подстроки или проверка на равенство меньше чем за O(S) в худшем случае никак не сделаешь.

#21
6:25, 30 ноя. 2018

=A=L=X=
> А ну то есть просто строка нужна сверхбыстрая по обозначенным операциям.
На простых операциях она, как раз, тормозить будет, по сравнению с обычными строками.
Но мне главное, чтобы тормоза не росли с ростом размера.

> нахождение подстроки меньше чем за O(S) в худшем случае никак не сделаешь.
Откуда ты взял это "нахождение подстроки"? У меня было только выделение, т. е. функция substr.
И обычный std::string_view эту задачу решает за O(1).

Кстати, S тут — это суммарный размер всех строк в программе.

#22
6:32, 30 ноя. 2018

}:+()___ [Smile]
> std::string_view эту задачу решает за O(1).

Ну можно и так сказать, cow строки с этим хорошо могут совладать.
Но сравнение уже нет. Хотя среднестатистическое сравнение вообще наверное как правило вырождается в O(1) на большинстве данных.
Так или иначе речь совсем не про "коллекцию строк", а про просто строку, а то путаницы из-за этих слов было вагон.

#23
6:33, 30 ноя. 2018

}:+()___ [Smile]
> Кстати, S тут — это суммарный размер всех строк в программе.

Вот опять внезапно оказывается, что ты нихрена не объяснил.
Откуда это то опять вылезло, из каких соображений?

#24
6:42, 30 ноя. 2018

=A=L=X=
> Хотя среднестатистическое сравнение вообще наверное как правило вырождается в O(1) на большинстве данных.
Нужно именно в наихудшем случае.

Фишка в том, чтобы O(L) из сравнения перенести в конструктор, где новую строку сравнить со всеми строками в системе и дедуплицировать, а в операции сравнения только вернуть кешированный результат.

> Так или иначе речь совсем не про "коллекцию строк", а про просто строку, а то путаницы из-за этих слов было вагон.
Именно что коллекция. Отдельные строки не получится ни сравнивать, ни удалять быстро. Обе операции надо амортизировать на всю коллекцию.

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

#25
6:48, 30 ноя. 2018

Suslik
> как я понял, он хочет свести задачу к дереву, в листьях которого хранятся
> только символы алфавита и далее все строки(ветки) составляются из них как из
> подстрок. каждый элемент дерева считается отдельным объектом и над ним
> подразумеваются операции, которые производятся над любой самостоятельной
> строкой.

Вот так наверное понял.
Да, задачка забавная.

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

#26
9:15, 30 ноя. 2018

Наверное, имеет смысл сразу закладываться в слоговые фрагменты, а не только отдельные символы.

#27
9:46, 30 ноя. 2018

Не понял что нужно Смайлу, но мнение имею.
А цепи Маркова под это дело нельзя приспособить? Правда память они жрут как не в себя...

#28
9:56, 30 ноя. 2018

youtube
> Не понял что нужно Смайлу, но мнение имею.

Попытаться сделать такую коллекцию строк, которая бы за счёт своей внутренней структуры серьезно упрощала многие операции со строками.
Например конкатенация строк вместо копирования символов возвращала бы такую строку которая бы просто хранила какая из уже существующих в коллекции строк является началом, а какая - концом. Или, например, сравнение на равенство осуществлялось бы за O(1) всегда, т.к. коллекция никогда не хранит дубликаты строк и таким образом равенство всегда приводит к идентичности адреса this строки и достаточно одной проверки.
Реализация может быть любой это просто примеры.

#29
10:14, 30 ноя. 2018

=A=L=X=
Читая твой пост подумалось что смайлу надо сжатие в реалтайме. Что-то какая-то божественная коллекция

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

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