Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Здравствуйте. Случайно наткнулся в журнале на задачи от одной компании, (название которой я писать не буду ибо не хочу что-то пиарить, пусть и на фоне), и решил размяться Да, решения этих задач можно отправить в компанию, не знаю зачем, какие-то призы вероятно, но срок уже истек, это сентябрьский номер, так что вы не подумайте что я преследую личную выгоду от того, что спрашиваю у вас что-либо по этому поводу. Вообще дано 6 задач. Сейчас решил первую. задача 1Дана строка "Hello, Embarcadero". Не обращая внимание на производительность, написать как можно больше вариантов , как поменять символы местами в обратном порядке. Варианты могут отличаться лишь синтаксисом. Можно использовать библиотечные функции работы со строками, но должны быть варианты и без них.\ Вот как я её решил 1 вариант Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 2 вариант, аналогично, но реализовал функцию strlen Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 3 вариант Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 4 вариант, тут добавил указатели Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. можно еще написать функцию принимающую адреса начала и конца строки, и делать её реверс, можно сделать реверс каждого слова, можно своп делать по-другому. Других вариантов в голову не приходит. Но ведь должен быть в задаче подвох ? Она кажется слишком простой. Как бы вы её решали ? Кстати, в условии задачи меня смутила фраза про производительность. Что авторы хотели этим сказать ? PS остальные 5 задач выложу позже. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 04:14 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
На производительность вляют столько факторов что топика не хватит. Я-бы предложил подумать над оптимизациями идущими далеко в будущее. 1) Всегда-ли нужно свапировать? Может быть строка уже зеркально-симметрична Я исхожу из предположения что запись в память - дорого стоит с точки зрения кешей и синхронизаций. И лучше ее (запись) вообще не делать до самого последнего времени. Максимальная иммутабельность. 2) Предлагаю вообще не свапировать длинные строки (более 255 символов к примеру). Но хранить для них булево свойство. Код: plaintext 1. Если кто-то если захочет получить распечатать строку на экране или получить перевёрнутый порядок - то мы ему отдадим геттер или итератор который вернёт символы в том порядке который соответствует isSwapped. Это отчасти соответствует принципам lazy-evaluation. Методы конкатенаций и поиска подстрок также должны учитывать свойство isSwapped. Предлагаю также считать верным тезисы Код: plaintext 1. Если строка - является палиндромом или из 1 символа то Код: plaintext 1. Признак палиндромности isPalindrom=true можно также хранить в объекте строки. 3) Возможно существуют и низкоуровневые (ассемблерные) оптимизации этой задачи основанные на знаниях команд современных CPU и возможностей железа в плане управления кешами. Вобщем у меня - всё. Задача в чистом виде - тоесть именно свапирование букв в memory мне кажется ненужной. Тем более что в форуме эта задача уже звучала. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 09:24 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Ну вы вообще... Не каждый сможет обратить строку, в смысле, делать это могут не только лишь все... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 11:05 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonНа производительность вляют столько факторов что топика не хватит. Я-бы предложил подумать над оптимизациями идущими далеко в будущее. Вообще-то в условии задачи прямо сказано что производительность не важна :) Это задача на умение генерировать идеи. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 12:07 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
А еще есть вариант рандомно перемешивать массив символов до тех пор, пока там не появится "строка наоборот". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 12:28 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Будь здесь Базист - он предложил-бы загнать все строки известные науке в его магическую флористическую базу и вместо реверса просто находить ответную строку через ультра-быстрый поиск. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 12:35 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
SashaMercuryНо ведь должен быть в задаче подвох ? Подвох номер 1: про системную функцию ReverseString() они не зря упомянули. Подвох номер 2: про "in-place" нигде не сказано, следовательно простейшим методом будет копирование в новый буфер. Ну и странно, что тебе не пришёл в голову простейший вариант: Код: sql 1. 2. 3. 4. 5. 6. 7. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 12:39 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakovследовательно простейшим методом будет что есть "простейший" ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 12:58 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Дима. Дык твой код вроде как сделает двойной реверс. Не? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 13:04 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonДима. Дык твой код вроде как сделает двойной реверс. Не? Обижаешь... Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 13:31 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Напомнило. Красивая формула. Код: plaintext 1. Я где-то читал что есть особая ассемблерная директива машин серии PDP которая 1:1 соответствует этой строке кода. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 13:45 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonБудь здесь Базист - он предложил-бы загнать все строки известные науке в его магическую флористическую базу и вместо реверса просто находить ответную строку через ультра-быстрый поиск. Лучше сделать мемоизацию. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 13:56 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonЯ где-то читал что есть особая ассемблерная директива машин серии PDP которая 1:1 соответствует этой строке кода. Есть. ЕМНИП: Код: sql 1. В машинном коде - 113130. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 13:59 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonНапомнило. Красивая формула. Код: plaintext 1. Я где-то читал что есть особая ассемблерная директива машин серии PDP которая 1:1 соответствует этой строке кода. Так и в интеле есть MOVS -- копирование строки заранее определённой длины. Она делает это вместе с охватывающим циклом. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 13:59 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonНапомнило. Красивая формула. Код: plaintext 1. Я где-то читал что есть особая ассемблерная директива машин серии PDP которая 1:1 соответствует этой строке кода. Зачем так далеко ходить? Интеловский MOVS умеет и ++ и -- :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 13:59 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Anatoly MoskovskyИнтеловский MOVS умеет и ++ и -- :) А умеет он их одновременно? Тогда задачу ТСа можно было бы решить в пять ассемблерных строчек. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 14:06 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Dimitry SibiryakovAnatoly MoskovskyИнтеловский MOVS умеет и ++ и -- :) А умеет он их одновременно? Тогда задачу ТСа можно было бы решить в пять ассемблерных строчек. Неа, не умеет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 14:07 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Да, тема действительно звучала. И я не вижу проблем в том, чтобы решить эту задачу. Меня и раньше, и сейчас, постоянно, смущает ограниченность. Мы в любом случае перебираем каждый байт. Увидел код копирования Марка строки r to l, и ваши комментарии о том, что существует ассемблерная команда позволяющая это сделать проще. Проще ли ? А эта команда всё-равно будет идти побайтово ? Вероятно так. В любом случае, у нас ограничения, и мы упираемся в эти O(n). А я хочу O(1). Было бы хорошо, если бы могли читать память в обратном порядке, но это позволило бы нам решить лишь часть задач. Например, у нас есть функция f(x)=x+3, и оператор Pz(x)=z(x)^2, т.о. Pf(x)=(x+3)^2, мы в одно действие получаем новое отображение, и нам не нужно менять значение каждой точки, было 3, теперь будет 9, было 4, теперь 16. Что-то аналогичное мне и хотелось увидеть в качестве алгоритма решения данной задачи ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 14:30 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
SashaMercuryА я хочу O(1) В любом случае для переворота должна быть прочитана вся строка и вся записана, а сколько и какие команды процессора понадобятся - неважно, т.к. сложность алгоритма это не изменит. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 15:05 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Хм... интересненько. CNU Clisp 2.49 Код: python 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 15:34 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Интересно где он декларирован? Искал через текстовый поиск по %LISP_HOME% но нашёл только использование реверса в других *.lisp файлах. Но нету в define/defun/def Может Илья подскажет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 15:46 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Dima TВ любом случае для переворота должна быть прочитана вся строка и вся записана Mayton выше привел алгоритм без копирования, с флагом. Так что не в любом случае. Надо просто шире думать :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 15:48 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Anatoly MoskovskyНадо просто шире думать :) Надо шире искать под какой ещё коврик замести потерю времени на реальный реверс. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 15:57 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Anatoly MoskovskyMayton выше привел алгоритм без копирования, с флагом.Чтобы выставить флаг, придётся "попарно сверить две половинки строки". И даже тогда может не повезти и копировать всё равно придётся.Надо просто шире думать :)Особенно надо думать о преждевременной оптимизации. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 16:00 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
SashaMercuryМы в любом случае перебираем каждый байтЭто пока вы не начали работать с кодировками. Тогда реверс байт будет простым и тривиальным занятием. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 16:02 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Basil A. SidorovЧтобы выставить флаг, придётся "попарно сверить две половинки строки". И даже тогда может не повезти и копировать всё равно придётся. Джава знает ответ на этот вопрос :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 16:03 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Anatoly MoskovskyДжава знает ответ на этот вопрос :)Нет, не знает. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 16:04 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Я когда-то приводил пример с транспонированием матрицы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 16:07 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
И что? Весь APL был сделан на отложенных вычислениях, но работало это только потому, что, как правило, требовалась только часть матрицы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 16:09 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Я Сашику вобщем-то писал. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 16:10 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Basil A. SidorovЧтобы выставить флаг, придётся "попарно сверить две половинки строки". И даже тогда может не повезти и копировать всё равно придётся. Погодите, причем здесь сравнение половинок? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 16:27 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Вы про разные флаги говорите наверное. Я их 2 штуки предлагал. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 16:35 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Похоже, что - да, про разные. Но "Swapped=False" - вообще хня. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 16:53 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Иммутабельность, мать ее так... Она заложена во все строковые объекты .Net/Java. Я просто предложил свой взгляд на задачу реверса в С/С++. А так - всё чики-пики. Можно и кувыркать символы в мемори. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 16:58 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonИммутабельность, мать ее так... Она заложена во все строковые объекты .Net/Java.Не знаю как в .NET, но в Java неизменяем только java.lang.String. А StringBuilder/StringBuffer - вполне переменные.Я просто предложил свой взгляд на задачу реверса в С/С++.Отложенный реверс - изначально задница: нет места отложенным вычислениям. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 17:06 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Basil A. Sidorov, StringBuffer, StringBuilder не являются строковыми переменными. Это хелперы которые помогают сформировать всё тот-же самый immutable String на выходе. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 17:42 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonЭто хелперы которые помогают сформировать всё тот-же самый immutable String на выходе.Если String нужен, да, могут быть приведены к строковому типу. А если не нужен: Код: java 1. 2. 3. 4. 5. ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 18:13 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Я слышу вопрос - "А не заменить-ли все String на StringBuilder" ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 18:16 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Basil A. Sidorov правильно упомянул про кодировки. Я тоже о них сразу подумал. Поменять однобайтные символы просто. А вот если будут многобайтные кодировки, UTF8 или UTF16 с суррогатными парами, то... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 18:36 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Плавающие кодировки существуют обычно в файлах. В String-объектах это обычно UTF-16. Индекс вычислется чутка легше чем в утф-8. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 19:00 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
mayton, да, но у автора голый Си. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 19:16 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
А что для Си не существует поддержки кодировок? В библиотеках хотя-б... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 19:18 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
petalvikПоменять однобайтные символы просто. А вот если будут многобайтные кодировки, UTF8 или UTF16 с суррогатными парами, то... ничего страшного. даже если на месте менять. и без всяких библиотек ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 19:24 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Тогда нужно 3 реверса. В скобках замечу что нет однозначных правил по детектированию чё внутри байтэррея. Код: plaintext 1. 2. 3. 4. 5. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 19:29 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
petalvikПоменять однобайтные символы просто. А вот если будут многобайтные кодировки, UTF8 или UTF16 с суррогатными парами, то...Да хоть UTF32. Составные символы никто не отменял. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.11.2014, 20:31 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Basil A. SidorovSashaMercuryМы в любом случае перебираем каждый байтЭто пока вы не начали работать с кодировками. Тогда реверс байт будет простым и тривиальным занятием. не говорю что это сложное занятие. Просто хочу решать эту задачу по-другому ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 01:51 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Придумал, так можно. А есть такой раздел в программировании исследующий именно методы чтения памяти через какие-либо функции, а не дублирование в том формате, что нам нужен. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 02:12 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Хм. Пришел к тому, что мне нужно реализовать тип данных который включает в себя строку, и способ её чтения ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 02:30 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
SashaMercuryХм. Пришел к тому, что мне нужно реализовать тип данных который включает в себя строку, и способ её чтения спецификацию юникода почитай - там много удивительного ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 03:03 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
ИзопропилSashaMercuryХм. Пришел к тому, что мне нужно реализовать тип данных который включает в себя строку, и способ её чтения спецификацию юникода почитай - там много удивительного процитируйте хотя бы строчку из "много удивительного" ;) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 03:10 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Изопропил, википедия, это не спецификация. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 03:33 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
SashaMercury, спецификацию сам откроешь - http://unicode.org UNICODE NORMALIZATION FORM http://unicode.org/reports/tr15/ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 03:40 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Изопропил, спасибо за ссылку. Но к сожалению, у меня нет 60-120 минут(а может и больше) на изучение того документа. Это не Си, и не алгоритмы, и не математика. Позже, я обязательно постараюсь прочитать то, к чему вы пытались меня привести. Может быть вы попробуете простыми словами донести до особо одарённых то, что хотели сказать ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 12:50 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Наверное он хотел сказать что сравнени Unicode символов не равно сравнению байтов. Если я верно понял суть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 13:58 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonНаверное он хотел сказать что сравнени Unicode символов не равно сравнению байтов. Если я верно понял суть. Ну да, и если крутить символы in-place, то будет сложнее -- символы-то переменной длины ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 14:10 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
а ещё два символа могут складываться в один знак (буква с диакритикой), так что надо ещё определиться, какой результат мы хотим увидеть после «кручения». ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 14:31 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
MasterZivНу да, и если крутить символы in-place, то будет сложнее -- символы-то переменной длины это самое простое, строку UTF-8 можно читать в любом направлении. а вот композитные(не путать с суррогатными парами UTF-16) типа a + ogonek + acute = <U+0061, U+0328, U+0301> переворачивать несколько сложнее ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 14:33 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Возможен ли вообще реверсный итератор по Utf-8 байтовому массиву? Это как архив читать в обратном направлении. Особенно в совокупности с копозитными символами. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 14:53 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonВозможен ли вообще реверсный итератор по Utf-8 байтовому массиву?Разумеется возможен. Отдельная кодовая точка состоит или из байта со сброшенным старшим битом или начинается байтом с двумя установленными старшими битами. Максимальный размер кодовой точки - четыре байта. Соответственно, при любом направлении прохода по последовательности байт отдельные кодовые точки выделяются с примерно одинаковой (не)эффективностью. Обработка составных символов от кодировки не зависит. Всё, что требуется - аккуратно копировать кусочки байт вперёд и назад. Не просто, но реализуемо. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 16:04 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Тоже думаю что возможно. Кстати думаю что с некоторой структурой данных типа индексации.. можно не реализовывать чтения Utf8 "взад". А просто "двигать" серединку строки влево. По аналогии с сортировкой вставками. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 16:12 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Изопропил, не улавливаю связи с тем, о чём я рассуждал. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 16:14 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonВозможен ли вообще реверсный итератор по Utf-8 байтовому массиву? тривиален - первый байт многобайтового символа 11xxyyyy все последующие 10xxyyyy ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 16:34 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
SashaMercuryИзопропил, не улавливаю связи с тем, о чём я рассуждал. Хотел строковую библиотеку написать? - не забудь про UTF-8. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 16:37 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Нет. Трудность не в том. Поддержка Utf-8 обычно реализована как фильтр внешних данных. А все манипуляции со строками в ядре системы должны ходить в Utf-16. А то чем мы щас занимаемся это онанизм и вариации на тему как-бы впихнуть "квадратную пробку в круглое отверстие". Вобщем сон разума порождает чудовищ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 16:42 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonА все манипуляции со строками в ядре системы должны ходить в Utf-16.Фундаментальное заблуждение. Корни растут из того факта, что изначально юникод делали по принципу "один символ - один код". Я бы сказал, что есть два варианта: 1. utf8; 2. Упаковка 21-битных триад в блоки по восемь байт. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 16:45 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
mayton, речь об интерпретации композитных символов. UTF-8 UTF-16 или UTF-32 не имеет ни малейшего значения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 17:24 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonА все манипуляции со строками в ядре системы должны ходить в Utf-16. Ну тогда уж UTF-32 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 17:25 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Basil A. Sidorov2. Упаковка 21-битных триад в блоки по восемь байт. Это еще зачем? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 17:52 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
ИзопропилmaytonА все манипуляции со строками в ядре системы должны ходить в Utf-16. Ну тогда уж UTF-32 Не очень понял сарказма. Кому не хватает 64К букв? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 17:52 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonНе очень понял сарказма. Кому не хватает 64К букв? алгоритму обработки. нечего ветви делать для обработки суррогатных пар. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 17:58 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonНе очень понял сарказма. Кому не хватает 64К букв?Если вы не в курсе, то уже третья версия юникода содержала более ста тысяч (несоставных) символов. Текущая версия - шестая. P.S. Собственно, 64КБукв не хватило уже тогда, когда Корея, Китай и Япония не договорились о единой схеме кодирования иероглифических символов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 18:28 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonЭто еще зачем?UTF-16 требует обрабатывать суррогатные пары, UTF-8 и UTF-32 - не требуют. В UTF-8 - переменное число байт на кодовую точку, в UTF-32 - фиксированное, но бесполезно теряется одиннадцать бит. Если упаковать 21-битные кодовые точки в битовую структуру, то мы оставляем фиксированное число бит на кодовую точку и достаточно существенно экономим на хранении данных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 18:32 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Basil A. Sidorovв UTF-32 - фиксированное, но бесполезно теряется одиннадцать бит. Если упаковать 21-битные кодовые точки в битовую структуру, то мы оставляем фиксированное число бит на кодовую точку и достаточно существенно экономим на хранении данных. Понятно. Почему-то напомнило Base64. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 19:13 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Долго пытался вспомнить применение реверсу. Что-то такое видел. В каком ЯП - не скажу точно. Толи делфи толи PowerBuilder Поэтому - псевдокод: Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 19:30 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Или так. Код: pascal 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 19:31 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonДолго пытался вспомнить применение реверсусам по себе реверс малоинтересен разбиение юникодной скроки на кластеры графем - интереснее ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 19:40 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonДолго пытался вспомнить применение реверсу. На собеседованиях могут спросить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 19:47 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
mayton, Код: plaintext 1. За такое сразу уволить без выходного пособия :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 19:55 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonИли так. Код: pascal 1. Тогда уж: Код: pascal 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 20:08 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
ИзопропилmaytonДолго пытался вспомнить применение реверсусам по себе реверс малоинтересен разбиение юникодной скроки на кластеры графем - интереснее Переход между big/little-endian можно считать реверсом. Вот еще кейс. По поводу графем - интереснее конечно только углубляться в эту тему как-то лень. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 21:23 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonПереход между big/little-endian можно считать реверсом.Нельзя. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 21:27 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Сама лаконичность! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 21:28 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Но если очень хочется то можно :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 21:33 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Ну-ну ... Высказать непродуманную мысль, конечно, можно, но хотелось бы услышать обоснование теоретической возможности сделать преобразование BE/LE на строке в кодировке UTF-8. Для простоты можно начать с обоснования если не эквивалентности, то хотя бы подобия изменения порядка байт и порядка символов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 21:44 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Да ладно не парься! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 21:48 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
И не думал. Просто страшно за неокрепшую психику молодёжи ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 26.11.2014, 21:51 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Во, наткнулся на реальное применение реверса строк: Код: sql 1. Это чтобы задействовался индекс. Пруф ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2014, 20:56 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
petalvik, ага. Я тоже эту тему вспомнил. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2014, 21:20 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
petalvikЭто чтобы задействовался индекс. Не, это чтобы не задействовалась первая НФ. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2014, 21:22 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Начиная с Oracle11g могли-бы virtual columns создавать. Туда - перевёрнутые имена почтовых доменов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.11.2014, 23:15 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Здравствуйте. Привожу третью задачу. (вторая позже) 3 задачаПроверить, является ли целое число счастливым билетом. Эта задача показалась мне слишком простой. Потому решил следующую задачу: Что на самом деле нужно решитьНайти количество счастливых билетов, входной параметр -количество символов в билете 2n. И тут я использовал длинную арифметику. Алгоритм решения привожу ниже: 1 часть все уже видели Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. 163. 164. 165. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. 180. 181. 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193. 194. 195. 196. 197. 198. 199. 200. 201. 202. 203. 204. 205. 206. 207. 208. 209. 210. 211. 212. 213. 214. 215. 216. 217. 218. 219. 220. 221. 222. 223. 224. 225. 226. 227. 228. 229. 230. 231. 232. 233. 234. 235. 236. 237. 238. 239. 240. 241. 242. 243. 244. 245. 246. 247. 248. 249. 250. 251. 252. 253. 254. 255. 256. 257. 258. 259. 260. 261. 262. 263. 264. 265. 266. 267. 268. 269. 270. 271. 272. 273. 274. 275. 276. 277. 278. 279. 280. 281. 282. 283. 284. 285. 286. 287. 288. 2 часть Основной алгоритм Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. ниже, скриншот для длины 1000 (n=500) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.12.2014, 09:58 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
А вот тесты этого кода аналогичной задачи ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.12.2014, 10:01 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Как бы вы решали эту задачу ? Мне кажется, что можно решить проще ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.12.2014, 10:02 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
Ты не поверишь. Эту задачу на SQL.ru тоже решали. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.12.2014, 10:23 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
petalvikmaytonДолго пытался вспомнить применение реверсу. На собеседованиях могут спросить. Я единственное что могу вспомнить/придумать -- для построения дерева суффиксов слов для полнотекстового поиска. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.12.2014, 12:25 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
На тему текстового поиска я заготовил замечательную задачку на пятницу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.12.2014, 12:28 |
|
||
|
Решение ряда задач.
|
|||
|---|---|---|---|
|
#18+
maytonТы не поверишь. Эту задачу на SQL.ru тоже решали. Кажется здесь было решение тривиальной алгоритмической задачи разными подходами и средствами . И где-то в МССКЛ-Ораклах мерялись длиной execution plan. Не помню точно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 02.12.2014, 13:42 |
|
||
|
|

start [/forum/topic.php?all=1&fid=57&tid=2019210]: |
0ms |
get settings: |
11ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
68ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
111ms |
get tp. blocked users: |
1ms |
| others: | 14ms |
| total: | 240ms |

| 0 / 0 |
