И отсюда же следует, что для поиска первого вхождения подстроки нужен массив только для паттерна. А для итерационного нахождения всех подстрок, считать, что паттерн совпал только что при продолжении поиска.
А вообще, огромное спасибо! Очень круто всё разложено по полочкам! Вы сделали моё утро!
На самом деле, если нет NaN, float легко сортировать как целые числа. Если только положительные, то вообще телодвижений делать не нужно.
Строки по первым символам тоже можно разбросать на мелкие бакеты, и потом применить обычную сортировку внутри бакетов. Правда, это если первые символы хоть как-то отличаются: массив интернетовских ссылок весь будет начинаться с http:// и https://
Помню, как восхищенно читал про dual-pivot и пытался его реализовать для Go. Но в итоге реализовал обычный, т.к. с интерфейсом, основанным на Less многовато сравнений выходило, а вокруг каверзных паттернов все равно ворк-эраунды приходилось строить.
Простите, но это не CPS. В CPS после вызова продолжения нет возврата в вызывавшую функцию, а у вас это везде. Т.е. tail call в продолжение - это не опциональная вещь, а обязательная. И defer тоже противоречит CPS.
CPS - это прежде всего способ либо промежуточного представления кода для оптимизации (доказано, что он эквивалентен SSA представлению), либо способ развертки синхронного кода в асинхронный (поищите CPC - Continuation Passing C).
Ещё, например, Chicken Scheme реализован через CPS: код Scheme транспиллится в C функции оригинального вида - функции всегда оканчиваются tail call в continuation и никогда не зовут return. Стэк растёт «бесконечно». А вернее, он параллельно используется как eden generation в GC, т.е. для аллокации объектов. И когда размер стэка доходит до предела, live объекты с него копируются в кучу, а стэк обрезается под корень (через longjmp). Не устаю восхищаться этим трюком.
Кстати, в Go тоже можно было бы реализовать через panic+recover. А в кучу Go и сам скопирует что нужно.
Я только после двух лет перестал хотеть уволить своего стажёра. Два года, чтобы из студента получился нормальный разработчик, за которым нужно проверять не каждую строчку подряд, а лишь каждую третью.
Ну, не на пуговицах. Все же хранение хранение сложных структур в скомпиленном бинаре и потом десериализация по требованию в рантайме заметно сложнее, чем просто строк.
Но согласен: это известная хотелка и недоумение пользователей языка. Парсить тэги самому кажется очень странным занятием.
Да, действительно такая схема есть, только ещё проще: не в битовые колонки, а в байтовые. И даже без предварительного XOR, емнип.
Если цель только сжать по сильнее, то это вполне рабочий вариант. Gorilla хороша тем, что для анализа значений не требуется предварительная распаковка всего массива. А классические алгоритмы сжатия требуют сохранять выходной буфер до окончания декомпрессии.
Хотя, конечно, можно сочетать этот подход с RLE + Хафман. Причём объединить байты и повторы в один алфавит для Хафмана. Тогда можно действительно доставать по байту из 8ми последовательностей и соединять в число. Это будет медленнее, чам Gorilla, но компрессия, наверное, будет лучше.
Датчик - это в широком смысле. Много разных показателей может быть в программах. Думать над каждым, как его представлять - пустая трата времени. Проще сказать: мы складываем в float/double с максимумом 20 бит мантиссы (что соответствует 6 знакам точности). А дальше уже умные алгоритмы сожмут это до приемлемых размеров.
А сжатие Гориллой тем и хорошо, что оно автоматически адаптируется к диапазону: ты можешь в него и миллисекунды выраженные в секундах складывать, и террабайты выраженные в байтах. Мосле xor экспоненты и те значения, и другие сожмутся примерно одинаково.
“Несовместимый сжатый формат” придумал Google. С тех пор его много где повторили. Повторили потому, что померили и увидели выгоду.
Произвольные вещественные числа действительно имеют много рандомных бит. Особенно, если десятичные дроби используются. Если же намеренно округлять до двоичных дробей (а когда ты сам делаешь датчики, то вполне можешь загрубить значения слегка), то нулей в хвосте получается много.
Сомневаюсь, что generic алгоритм сжатия нормально сожмёт. Во-первых, сжатие работает побайтово, а тут границы повторов на байты не выровнены. Во-вторых, повторы достаточно маленькие, и кодирование повторов плохо сжимается обычно.
Кроме степени компрессии играет роль, во-первых, скорость сжатия/разжатия, а во-вторых, возможность использования разжатых чисел немедленно, один-за-другим, без ожидания разжатия всего входного буфера, и без выходного буфера в принципе.
Примечательно, что один из непосредственных предков Lua был как раз языком конфигурации. И это до сих пор отражено в синтаксисе: вызов функции с одним параметром без скобок родом оттуда.
И отсюда же следует, что для поиска первого вхождения подстроки нужен массив только для паттерна. А для итерационного нахождения всех подстрок, считать, что паттерн совпал только что при продолжении поиска.
А вообще, огромное спасибо! Очень круто всё разложено по полочкам! Вы сделали моё утро!
На самом деле, если нет NaN, float легко сортировать как целые числа. Если только положительные, то вообще телодвижений делать не нужно.
Строки по первым символам тоже можно разбросать на мелкие бакеты, и потом применить обычную сортировку внутри бакетов. Правда, это если первые символы хоть как-то отличаются: массив интернетовских ссылок весь будет начинаться с http:// и https://
Я читал, что он был не главным и не самым активным.
Но одним из трёх, так что это всё равно потеря.
Помню, как восхищенно читал про dual-pivot и пытался его реализовать для Go. Но в итоге реализовал обычный, т.к. с интерфейсом, основанным на Less многовато сравнений выходило, а вокруг каверзных паттернов все равно ворк-эраунды приходилось строить.
И всё равно продолжаю восхищаться.
Ещё забыли модель итераторов Lua.
Простите, но это не CPS. В CPS после вызова продолжения нет возврата в вызывавшую функцию, а у вас это везде. Т.е. tail call в продолжение - это не опциональная вещь, а обязательная. И defer тоже противоречит CPS.
CPS - это прежде всего способ либо промежуточного представления кода для оптимизации (доказано, что он эквивалентен SSA представлению), либо способ развертки синхронного кода в асинхронный (поищите CPC - Continuation Passing C).
Ещё, например, Chicken Scheme реализован через CPS: код Scheme транспиллится в C функции оригинального вида - функции всегда оканчиваются tail call в continuation и никогда не зовут return. Стэк растёт «бесконечно». А вернее, он параллельно используется как eden generation в GC, т.е. для аллокации объектов. И когда размер стэка доходит до предела, live объекты с него копируются в кучу, а стэк обрезается под корень (через longjmp). Не устаю восхищаться этим трюком.
Кстати, в Go тоже можно было бы реализовать через panic+recover. А в кучу Go и сам скопирует что нужно.
Я только после двух лет перестал хотеть уволить своего стажёра. Два года, чтобы из студента получился нормальный разработчик, за которым нужно проверять не каждую строчку подряд, а лишь каждую третью.
ЕМНИП, у jpeg2000 были серьезные проблемы с лицензией. Т.е. он (был?) далеко не «бесплатный» и не «свободный».
Если я правильно понимаю статью, jpegxl лишён этого фатального недостатка. Но могу ошибаться.
Ну, не на пуговицах. Все же хранение хранение сложных структур в скомпиленном бинаре и потом десериализация по требованию в рантайме заметно сложнее, чем просто строк.
Но согласен: это известная хотелка и недоумение пользователей языка. Парсить тэги самому кажется очень странным занятием.
Да, действительно такая схема есть, только ещё проще: не в битовые колонки, а в байтовые. И даже без предварительного XOR, емнип.
Если цель только сжать по сильнее, то это вполне рабочий вариант. Gorilla хороша тем, что для анализа значений не требуется предварительная распаковка всего массива. А классические алгоритмы сжатия требуют сохранять выходной буфер до окончания декомпрессии.
Хотя, конечно, можно сочетать этот подход с RLE + Хафман. Причём объединить байты и повторы в один алфавит для Хафмана. Тогда можно действительно доставать по байту из 8ми последовательностей и соединять в число. Это будет медленнее, чам Gorilla, но компрессия, наверное, будет лучше.
А вас ни кто и не заставляет его разделять. Не нравится, не используйте/не следуйте этому подходу.
А другие экономят своё время и довольны этим.
Датчик - это в широком смысле. Много разных показателей может быть в программах. Думать над каждым, как его представлять - пустая трата времени. Проще сказать: мы складываем в float/double с максимумом 20 бит мантиссы (что соответствует 6 знакам точности). А дальше уже умные алгоритмы сожмут это до приемлемых размеров.
А сжатие Гориллой тем и хорошо, что оно автоматически адаптируется к диапазону: ты можешь в него и миллисекунды выраженные в секундах складывать, и террабайты выраженные в байтах. Мосле xor экспоненты и те значения, и другие сожмутся примерно одинаково.
Повторю: https://habr.com/ru/companies/sportmaster_lab/articles/834840/#comment_27144872
“Несовместимый сжатый формат” придумал Google. С тех пор его много где повторили. Повторили потому, что померили и увидели выгоду.
Произвольные вещественные числа действительно имеют много рандомных бит. Особенно, если десятичные дроби используются. Если же намеренно округлять до двоичных дробей (а когда ты сам делаешь датчики, то вполне можешь загрубить значения слегка), то нулей в хвосте получается много.
Сомневаюсь, что generic алгоритм сжатия нормально сожмёт. Во-первых, сжатие работает побайтово, а тут границы повторов на байты не выровнены. Во-вторых, повторы достаточно маленькие, и кодирование повторов плохо сжимается обычно.
Кроме степени компрессии играет роль, во-первых, скорость сжатия/разжатия, а во-вторых, возможность использования разжатых чисел немедленно, один-за-другим, без ожидания разжатия всего входного буфера, и без выходного буфера в принципе.
Видимо, когда в Google разрабатывали алгоритм, их данные имели много повторений. Возможно, они снимали показания быстрее, чем они менялись.
Примечательно, что один из непосредственных предков Lua был как раз языком конфигурации. И это до сих пор отражено в синтаксисе: вызов функции с одним параметром без скобок родом оттуда.
Только сегодня наконец прочитал успевшую стать классикой “Parse, don’t Validate”, и тут ещё одна статья с таким же посылом.
Не факт.
С переменной выглядит приятнее.
Простите, но вы решили другую задачу: вы заменили символы на позициях. А нужно было вставить.
Rust, Zig, свежие стандарты C и C++