Комментарии 15
Не удивлюсь, если в будущем выяснится, что все это - социальный эксперимент. Закинули удочку и смотрят, что получится. :)
Почему не использовать Span вместо самодельного StringPart?
Если вы знаете, как это сделать, и покажете мне это — буду очень благодарен.
(Посмотрев ваш код на гитхабе) Ваш StringPart
-- класс, поэтому ничего вы "на стэке" не храните. Стандартным решением было бы выделить некий буфер размера N
, используя либо stackalloc char[N]
либо ArrayPool.Shared<char>.Rent(N)
, после чего его можно кромсать и выдавать Span<char>
во временное пользование. В определенном случае это все можно запихать на стэк и действительно иметь 0 аллокаций для выполнения всяких операций над текстом.
Конечно не получится реализовать метод Split
потому что ref structs не могут быть generic параметром, но можно например вернуть коллекцию Range
, по которой вызывающий метод может из исходной строки нарезать подстроки,
foreach(var itemRange in myCharSpan.Split(...))
{
var subSpan = myCharSpan[itemRange];
// Do work on substring
}
И ваш RelativeStart
/RelativeEnd
очень похожи на Index
.
Ваш StringPart — класс, поэтому ничего вы «на стэке» не храните.
Какую ветку вы смотрели? Их там несколько, и попытка обойтись без StringPart (заменена на ReadOnlyMemory) реализована только в одной, netstd21. А массив на стек там действительно запихнуть не удалось
Конечно не получится реализовать метод Split потому что ref structs не могут быть generic параметром, но можно например вернуть коллекцию Range
А где эта коллекция в памяти будет?
Я смотрел только дефолтную ветку.
А где эта коллекция в памяти будет?
Зависит от того, как напишите. Range
и Index
это структуры. Вы можете a) завести запуленный массив и можете его переиспользовать. При вызове foreach
по массиву вы получите оптимизированный энумератор-структуру, и сможете по нему проитерировать без лишних аллокаций (*). Альтарнативно, можно выделить память под коллекцию рэйнжей на стэке.
Вообще, вот вам рабочий пример (**). Под все выделяется место на стэке, есть пространство для оптимизации, но свою задачу выполняет.
(*) - по карйней мере на первый взгляд
(**) - вроде как все эдж кейсы покрыты, но это неточно
К сожалению, под текущий алгоритм это не совсем подойдет — там в одном месте добавляется подстрока из строки-константы («0»), а не из исходной строки. Но можно подумать, как это обойти красиво (не хотелось бы явный костыль лепить).
Спасибо.
PS Коллекцию в таких случаях IMHO лучше прямо называть массивом: массив — это цельный кусок памяти (для размещения на стеке это существенно), а коллекция — совсем не обязательно.
Так и вам массив необязателен. Вы можете возвращать что-то, что имеет GetEnumerator<T>()
возвращающий хороший struct энумератор и IEnumerable<T>.GetEnumerator<T>()
для реализации интерфейса. С помощью такой штуки можно без лишних аллокаций итерировать любые коллекции, хоть спэны, хоть массивы, хоть связныые списки.
К сожалению, под текущий алгоритм это не совсем подойдет — там в одном месте добавляется подстрока из строки-константы («0»), а не из исходной строки. Но можно подумать, как это обойти красиво (не хотелось бы явный костыль лепить).
Ну если уж совсем хотите упороться, можно в конец исходной строки дописать константные подстроки. В Split
передать только слайс оригинальной строки, а затем в коллекцию рэйнжей добавить рэйнж на кусок строки, сожержащий константу. А если где-то нужно будет собрать это все воедино, то спэн рэйнжей просто будет указывать, какие кусочки большого буфера в каком порядке складывать. Можно сделать какой-нибудь ValueStringBuilder
и в него (тоже на стэке, например), собрать какой-то результат, и только на выходе получть строку. В промежутке не выделив ни одного лишнего байта (если все буферы умещаются на стэке).
Так и вам массив необязателен.
Но мне его достаточно. Списки, деревья и т.д. в данной задаче не требуются.
И вообще ;-) «Как все настоящие программисты знают, единственной полезной структурой данныхя вляется массив.» (отсюда)
Ну если уж совсем хотите упороться, можно в конец исходной строки дописать константные подстроки.
Мне эта идея тоже в голову сразу пришла. Только вот где эта строка с дописанными константами будет, а? В куче она будет, в мусор потом пойдет.
А вообще мне тут не багу на бою править, так что есть время подумать. Подумаю, если что-то придумаю — закоммичу на Гитхаб и допишу UPD в статью.
Ещё раз благодарю.
Там же где и основная -- на стэке. Если строки понятной длины (и разумной), например 256 символов или меньше, то можно не опасаясь выделить на стэке `stackalloc char[512]`, это всего 1 Кб. Вряд ли вы сможете так спровоцировать оверфлоу. А дальше пишите с начала буффера вашу входную строку, потом дописываете константные строки и все.
Разумеется это все ради спортивного интереса. Оптимизировать так без бенчмарка -- это искать себе проблем.
Если строки понятной длины (и разумной)
«Если.»© Длина исходной строки расписания в задаче не лимитирована.
Разумеется это все ради спортивного интереса.Ну да. И вся статья — тоже.
А оптимизация здесь — чисто исходя из «стек — хорошо, куча — плохо». Но это неточно, и внезапно, таки да, может оказаться «стек — хорошо, куча — лучше».
У меня не было времени прочитать статью до конца. "Не лимитирована" -- понятие растяжимое. Например, если в 99% случаев строка умещается в условные 256 символов, то можно использовать стэк, в остальных случаях -- пулить массив, это тоже фактически бесплатно. Запуленный массив можно точно так же передавать везде как спэн, поэтому алгоритм можно написать единожды. В этом вся прелесть спэнов.
Regular expression и стандартные функции автор не использует. А почему?
Старое доброе ООП: решаем тестовое задание