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

Задачка по алгоритмам

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

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

Короче задача:
Надо придумать организацию коллекции строк (набора байтов произвольной длины) так, чтобы операции конкатенации, выделения подстроки, лексикографического сравнения и удаления из коллекции выполнялись за O(logS), где S —полный размер коллекции, а операция добавления в коллекцию строки длиной L — за O(LlogS). Возможно ли это, в принципе, и если да, то как?
Вместо логарифма сойдет любая другая превдоконстантная асимптотика.


#1
0:39, 30 ноя. 2018

}:+()___ [Smile]
> Надо придумать организацию коллекции строк (набора байтов произвольной длины)
Байты строки могут лежать произвольным образом?

#2
1:29, 30 ноя. 2018

1 frag / 2 deaths
> Байты строки могут лежать произвольным образом?
Да. Собственно, задача и состоит в том, чтобы придумать, как хранить строки.
По идее, строка должна быть чем-то типа дерева из кусков.

#3
(Правка: 1:59) 1:55, 30 ноя. 2018

}:+()___ [Smile]
> лексикографического сравнения .... выполнялись за O(logS), где S —полный размер коллекции
Такое вообще возможно? Может быть ты имел ввиду O(L) где L - размер меньшей строки? Ну то есть L же вроде как там полюбому будет.

Ну и это. Префиксное дерево не подходит?

#4
2:15, 30 ноя. 2018

MrShoor
> Такое вообще возможно?
Дедупликация при вставке плюс объединение совпадающих поддеревьев.
Т. е. мы уже к моменту сравнения знаем, что большие куски строк одинаковые и спускаясь по дереву находим различающийся лист.

> Ну и это. Префиксное дерево не подходит?
Там же все операции O(L) вроде, не?

#5
2:26, 30 ноя. 2018

}:+()___ [Smile]
> Там же все операции O(L) вроде, не?
Угу, но я предложил потому что изначально не совсем понял, что тебе нужно.

#6
(Правка: 3:27) 3:26, 30 ноя. 2018

}:+()___ [Smile]
> операции конкатенации, выделения подстроки, лексикографического сравнения и
> удаления из коллекции выполнялись за O(logS), где S —полный размер коллекции
поясни на примере, как можно две строки конкатенировать за O(log n), где n — суммарная длина? под конкатенацией подразумевается создание непрерывного куска в памяти, содержащего результат, или, грубо говоря, random access итератор по результату?

#7
(Правка: 3:55) 3:52, 30 ноя. 2018

Suslik
> поясни на примере, как можно две строки конкатенировать за O(log n), где n — суммарная длина?
Если у нас строки в виде деревьев, то надо создать корневую ноду со ссылками на деревья исходных строк.

> под конкатенацией подразумевается создание непрерывного куска в памяти, содержащего результат, или, грубо говоря, random access итератор по результату?
Нет, надо просто получить объект в системе, который соответствует сумме двух других объектов.

И да, я не написал про доступ к строкам.
Соответственно, получение длины строки и символа под номером N тоже должно выполнятся за O(logS).

#8
4:04, 30 ноя. 2018

}:+()___ [Smile]
то есть тебе не строки нужны в C-смысле, а итераторы по строкам. random-access итератор с логарифмической сложностью доступа.

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

Suslik
> то есть тебе не строки нужны в C-смысле, а итераторы по строкам. random-access итератор с логарифмической сложностью доступа.
Не просто итераторы. Мне нужны именно операции над строками за псевдоконстантное время.

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

#10
(Правка: 4:39) 4:36, 30 ноя. 2018

}:+()___ [Smile]
тогда всё равно не понял. вот, допустим, есть у тебя K строк в коллекции. будем их просто хранить в памяти как массив строк. что именно означает конкатенировать две строки i и j? просто взять символ результирующей строки можно за O(1). за то же время можно добавить в коллекцию новую строку. а построить полученную конкатенацией строку непрерывным куском в памяти быстрее O(N) ну никак не получится. я не совсем понимаю, в каком именно формате ты ждёшь выходные данные от своей структуры данных.

UPD: а, я, кажется, понял. если тебе нужно просто получить объект "конкатенация строк i и j", то это тоже всегда можно сделать хоть за O(1). но чтобы из этого получить какую-то пользу, надо обозначить, как часто ты захочешь resolve'ить объекты из своей структуры данных в именно строки и за какую сложность. то есть нужно ввести операцию преобразования внутреннего представления строки в обычную непрерывную в памяти C-строку и соответственные ограничения на неё.

#11
(Правка: 4:53) 4:48, 30 ноя. 2018

например, можно сделать примерно так:

struct Substring;
{
  size_t srcStringId;
  size_t startOffset, endOffset;
}
struct String
{
  std::vector<Substring> substrings;
  size_t Resolve(char *dst)
  {
    size_t currOffset = 0;
    for(auto substring : substrings)
    {
      if(data->IsLeaf(substring.srcStringId))
      {
        //data — общее хранилище, хранит в себе все строки
        std::copy(dst + currOffset, data->GetLeafData(subsrting.srcStringId) + substring.startOffset, substring.endOffset - substring.startOffset);
        currOffset += substring.endOffset - substring.startOffset;
      }
      else
        currOffset += data->GetString(substring.srcStringId).Resolve(dst + currOffset);
    }
    return currOffset;
  }
};
Тут очень грубый набросок, без оптимизаций, но идея в том, что в каждом элементе, индексируемом через size_t id хранится либо лист — обычная C-строка, либо узел (конкатенация подстрок других узлов). Чтобы извлечь C-строку, используется рекурсивный метод Resolve(), который, собственно, копирует данные.  В этой реализации Resolve() позволяет только копировать всю строку целиком, по идее нужно копировать именно нужный интервал.

Если не жалко памяти, то можно делать оптимизирующие проходы как в алгоритмах вроде Disjoint set union — идея в том, что после каждого Resolve() для каждой подстроки ты меняешь её тип с ветки на лист, то есть копируешь в неё полученные данные в явном виде. Таким образом сложность последующих обращений к этой же строки уже будет константная.

#12
4:54, 30 ноя. 2018

https://en.wikipedia.org/wiki/Rope_%28data_structure%29 всё вроде ок, кроме сравнения. Гм.

#13
4:57, 30 ноя. 2018

А, тю.
Храним rope, и отдельно - отсортированный список наших строк. Сравнение за O(log N) тупо поиском в этом списке.
Раз уж ты допускаешь медленное добавление.

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

> отсортированный список
Ну, в смысле, сбалансированное дерево.

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