Комментарии 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 и стандартные функции автор не использует. А почему?
Публикации
Старое доброе ООП: решаем тестовое задание