Для чего вы используете перестановку строк? [закрыто]

15

В PHP это strrev(), в Rails это .reverse, но большинство языков не имеют функции обратного преобразования строк. Некоторые из них имеют функции обратного массива, которые можно использовать для символов. Я думал, что это должно быть серьезным упущением, но потом мне пришло в голову, что бы вы на самом деле использовали реверс строки ???

Единственный раз, когда я думаю, что видел это в демонстрациях и уроках, чтобы включить «Hello World!» в "! dlroW olleH".

Мой вопрос Есть ли смысл переворачивать строку или это совершенно бессмысленно?

,

добавление

Было гораздо больше ответов, которые я ожидал, и не все они были полностью академическими. Я бы вложил деньги, чтобы никто не смог придумать законный пример. Я также не думал, что узнаю что-то новое, но предложение Регламента Марка Канласа просто блестяще, и я с нетерпением жду возможности, чтобы он проявил себя. Спасибо всем.

clockworkgeek
источник
@clockworkgeek - если вы попросите кандидата сделать перестановку строк на своем любимом языке, вы удивитесь, если многие из них не придумают базовую функцию, которую вы упомянули. Тогда сколько не может придумать цикл, чтобы реализовать его самостоятельно.
Юстект
@justkt - это совсем другой вопрос, который может возникнуть, но вместо этого он может стать темой для TopCoder.
Clockworkgeek
6
Чтобы отправить текстовое сообщение, которое можно было бы прочитать в зеркале заднего вида во время вождения, чтобы полицейские не заметили.
JeffO
@justkt - если бы мне пришлось написать итеративный цикл, я бы начал с противоположных концов менять местами символы, пока не будет достигнута середина. Но тогда как вы меняете два значения? Вот просто лучший ответ, который мне когда-либо давали:a ^= b; b ^= a; a ^= b;
clockworkgeek
1
я использую перестановку строк для перестановки строк;)
Muad'Dib

Ответы:

19

Sexegers

Иногда проблемы, связанные с регулярными выражениями, легче записать, если перевернуть входную строку и решить проблему другим способом.

Техника вежливости человека, который научил меня Perl.

Sexeger на PerlMonks

Марк Канлас
источник
Спасибо. Очень удобный трюк для поиска чего-то последнего. Верно подмечено.
Clockworkgeek
Я делал это годами. Помогает в разборе адресов электронной почты.
Sal
23

Ну, это насмешливый ответ.

«Назад в прошлое» У меня была коробка Unix, и в ней был упорядоченный файл словаря английских слов, используемый для проверки орфографии.

Я создал новый файл, перевернув все слова в словаре, отсортировав их, а затем снова перевернув их. Результатом стал список слов, отсортированный справа налево.

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

Вы можете по-настоящему развлечься, когда увидите, что рифмуется с чем.

Майк Данлавей
источник
13

Я был программистом / разработчиком / системным администратором в течение ~ 10 лет, и я не могу вспомнить, чтобы мне когда-либо приходилось менять строки в реальных жизненных ситуациях.

Единственный непосредственный вариант использования, о котором я могу подумать, - это преобразование на основе чисел: выполненное наивно, процедура возвращает обратную строку. Однако, потратив немного математики, вы можете заранее рассчитать необходимое количество места, чтобы вы могли начинать заполнять буфер с конца.

zvrba
источник
1
Возможно, математика стоит дороже, чем перестановка строки, поэтому после тестирования производительности на вашей платформе (ARM, MIPS, x86) вы можете использовать перестановку строк. Может быть.
Зан Рысь
Вы можете заполнить буфер с конца и использовать a memmoveдо начала, когда закончите. Вероятно, это дешевле, чем вычисление log (n) / log (base) для вычисления необходимого количества цифр.
Патрик Шлютер
12
public bool IsPalindrome(string toCheck)
{
    return toCheck == toCheck.Reverse();
}
Скотт Уитлок
источник
1
Да, у нас на самом деле есть собеседование, где кандидаты пишут палиндром, и большинство из них делают это. Тем не менее, я , как это лучше , когда кандидаты итерации от 0к n/2и сравнить характер на противоположном конце.
Николь
@Renesis: Вы также можете сделать: установить p начало строки, q конец строки, while ( (*p == *q) && (p <= q) {p++; q--} return p > q;на C и других языках указателя.
Майкл К
4
Я полагаю, что хотя «проверка палиндрома» не особенно полезна, «написать проверку палиндрома», по крайней мере, имеет цель.
часовой механизм
2
Во время интервью они попросили меня перевернуть строку и сказали: «Запомни это без строки. Обратный ()». Поэтому я просто преобразовал строку в массив символов и сделал Array.Reverse
Джек Маркетти
Это довольно нишевое использование, и вы бы не сказали, что его стоит включить в язык / библиотеку!
Дэн Дип
8

Интервью!

Обратная строка (на месте или нет) - очень распространенный вопрос для получения базовых знаний по программированию. Язык, на котором отсутствуют эти встроенные функции, будет сложно взять на собеседование. Кандидат на самом деле должен что-то знать. 1


1: Это насмешливый ответ.

Джош К
источник
6

Я видел ситуации, когда настольное приложение общалось со встроенными устройствами и постоянно переключало порядок байтов, а данные перемещались в виде строк. Это об этом для меня, хотя.

Я бы не использовал строки для этого приложения, но так оно и было .....

как зовут
источник
+1 за этот ответ. Это, по крайней мере, практический пример, хотя я бы тоже сделал это по-другому, возможно, выбрав примитивные типы, по-разному enddian.
Clockworkgeek
5
<span style="unicode-bidi: bidi-override; direction:rtl;">
    <?php echo strrev($emailaddress); ?>
</span>

Не лучшее решение для запутывания адреса электронной почты, так как при добавлении его в буфер обмена он все равно переворачивается. И, если он станет популярным, его скоро обнаружат роботы-скребки по электронной почте.

Тем не менее, это было предложено .

Николь
источник
1
И самое популярное запутывание в использовании было дано только одно предложение во всей этой статье ... Кодирование в виде изображения.
Clockworkgeek
1
@clockworkgeek, он может быть популярным, но ИМХО это худшее из эффективных решений - его не так просто создать, он не встроен в HTML (скорость, хранение изображений, загрузка сервера), выглядит неуместно, не может быть стилизован с CSS, и таким же плохим пользовательским опытом, как обращение строк, необходимость запоминать и перепечатывать. И, вероятно, больше проблем, о которых я не думаю.
Николь
Любопытно, однако, что использование AT и DOT, которые легче всего декодировать для комбайна, оказывается почти идеальной эффективностью в предотвращении сбора урожая. Иногда держать это просто не такая плохая идея.
Джори Себрехтс
5

ASCII не лучшая кодировка для генетической информации (вы можете упаковать базовые типы ACGT как 2-битные). Упакуйте их в массив длинных, и вы получите 32 генетических "буквы" за слово. ДНК можно перевернуть, так что вы должны проверить кусок ДНК на предмет того, что обе передние являются обратными копиями тестовой последовательности. Таким образом, возможность инвертировать упакованную строку из 2-битных величин может быть очень полезна для различных видов генетического анализа.

В качестве эталона для шпионских агентств у меня был вопрос, как быстро вы можете поменять биты на длинные-длинные (на самом деле очень длинный набор длинных-длинных). Очевидный метод обмена 2 бит за раз намного медленнее, чем менее очевидные методы. Они связаны с некоторыми из аккуратных алгоритмов для транспонирования массива на месте.

Тангурена: Операция, на которую вы ссылаетесь, называется подсчетом населения. Аналогичные пожелания для битовых данных являются ведущими и конечными нулями. Есть много действительно хороших вещей, которые можно сделать с битовыми данными. Одна длинная операция - это параллельная передача данных на 64 пути, поэтому, если вы знаете, что делаете, вы можете получить невероятную производительность для некоторых типов вычислений.

Омега Центавра
источник
Интересная тема, как бы вы поменяли немного поля?
Clockworkgeek
"Как бы вы изменили битовое поле?"
Омега Центавра
2
Одним из подходов является поиск в таблице. Вы можете перевернуть байт, используя таблицу. Таким образом, вы можете сделать это на отдельных байтах. Есть также способы переместить несколько битов и один раз ... Немного хитрости и компромиссов (размер таблицы в зависимости от количества операций и т. Д.), И вы можете попытаться настроить его.
Омега Центавра
5

Все, где работать с обращенной строкой легче.

Работать с целыми числами в виде строк намного проще, если строки переворачиваются. Я построил некоторые библиотечные функции для выполнения математических операций с большими целыми числами и использовал обращение строк, чтобы упростить арифметические функции.

Конечно, я использовал его только для получения ответов на Project Euler, но, тем не менее, первоначальная предпосылка верна.

секира
источник
+1. при использовании строковых представлений чисел обратное представление очень полезно. и обычно стандартная библиотека будет представлять числа в обычном порядке.
back2dos
3

Возможно, недорогая многоязычная поддержка для языков, которые используют буквы справа налево (например, арабский), а не слева направо. Конечно, вы должны остерегаться символов акцента, изменяющих правильный символ ...

Циклоп
источник
2

Я не знаю, может быть, у кого-то есть жгучая необходимость проверить палиндром ....

Я не думаю, что это совершенно бесполезно, так как могут быть ситуации, когда нужно иметь возможность перевернуть строку.

Темная ночь
источник
Следующим вопросом будет, когда вам когда-нибудь нужно было проверять палиндром в реальном мире? Опять же, я когда-либо видел, чтобы кто-то заботился об уроках алгоритма.
Clockworkgeek
как это, например: jimsabo.com/palindrome.html
Darknight
Я думаю, что есть, вероятно, другие применения, но это зависит от домена. Например, если поиск строк был оптимизирован для прямого поиска, и вы хотели выполнить несколько поисков для последнего вхождения, вы можете сначала отменить его. Это было бы оптимизацией, и не должно быть сделано, если для этого нет доказуемого случая. Я мог бы представить алгоритм для генерации хеш-функции из строкового значения, который хотел бы использовать хвостовую часть, возможно, обращенную, если это обеспечивало лучшие характеристики хеширования.
Скотт Уитлок
2

При обработке и анализе естественного языка иногда проще искать строку от конца до начала. Обратная строка была бы полезна для отладки или в качестве альтернативного способа написания цикла (переверните строку, а затем выполните цикл от индекса 0 до n-1).

Также некоторые языки пишутся справа налево, поэтому для этого можно использовать преобразователь строк, если вы находитесь в среде, которая изначально не распознает языки LTR / RTL.

Строка (в некоторых языках) - это массив символов, но это могут быть также чеки или модификации инвентаря. В цикле, проходящем через них, вы можете выполнять некоторые вычисления, которые должны быть одинаковыми, независимо от того, в каком порядке вы их обрабатываете. Совершенно громоздким модульным тестом было бы проверить, применяют ли они те же вычисления в прямом или обратном направлении. Это может быть тривиально очевидно для добавления, а может и не для других более непрозрачных операций.

MatthewMartin
источник
1

Для компиляторов?

Это забавно, но большинство символов в языке начинаются с общего шаблона. Я не говорю здесь о венгерской нотации, но если вы подумаете о пространстве имен / классах, то многие символы на самом деле будут иметь общий префикс .

myproject::SomeClass::GetFoo
myproject::SomeClass::GetBar

Проблема в том, что при выполнении бинарного поиска обычные префиксы - это наихудшая вещь, с которой вы можете столкнуться, потому что вам придется сравнивать эти префиксы снова и снова.

С другой стороны, если вы посмотрите на струны задом наперед, вы увидите гораздо больше энтропии! И тогда внезапно бинарный поиск (через Trie) становится намного более мощным!

Меня всегда беспокоило, что искаженные имена C ++ (от gcc) не были изменены, чтобы поместить пространство имен LAST :)

Матье М.
источник
0

Я переворачиваю телефонные номера и определенные строки для поиска время от времени

дон
источник
0

Единственный раз, когда я могу вспомнить, что использовалась перестановка строк, была функция, которую я видел в далеком прошлом, которая использовала ее при разборе имен файлов, чтобы гарантировать, что '.' он нашел в имени файла фактически последнюю точку, которая отделяла имя файла от расширения. то есть, анализируя имя файла, например data.2010.12.08.dat, вы бы перевернули строку, нашли первую точку, вычлили эту позицию из конца исходной строки и взяли подстроку. Я не говорю, что это оптимальный способ сделать это, но это то, что он сделал. Возможно, это было в Powerbuilder, где такое странное использование функций было обычным для обхода различных неочевидных проблем.

GrandmasterB
источник
0

Единственное реальное приложение для работы с червями, которое я видел при использовании strrev, - это сохранение в базе данных паролей пользователей, которые «не читаются» ...

Но я помню, что в C есть шаблон для использования strrev, может быть, я придумаю его позже.


источник