Вы не сможете решить эту задачу на собеседовании

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

Прежде всего — немного истории. Работая на должностях тимлида и техлида мне порой приходилось проводить собеседования, соответственно нужно подготовить несколько теоретических вопросов, ну и пару несложных задач, на решение которых не должно было бы уйти больше 2х-3х минут. Если с теорией все просто — мой любимый вопрос это: «чему равен typeof null?», по ответу сразу можно понять, кто сидит перед тобой, джун — просто правильно ответит, а претендент на сеньера, еще и объяснит почему. То с практикой — сложнее. Я долго не мог придумать нормальное задание, не изъезженное, типа fizz-buzz, а что-нибудь свое. Поэтому я на собеседованиях давал задания, которые сам проходил, устраиваясь на текущую работу. О первом из них и пойдет речь.

Текст задачи


Напишите функцию, которая принимает на вход строку, а возвращает эту строку «задом наперед»

function strReverse(str) {};
strReverse('Habr') === 'rbaH'; // true

Очень простая задача, решений для которой масса, самым оптимальным для себя я долго считал такое решение:

const strReverse = str => str.split('').reverse().join('');

Но что-то меня в этом решении смущало всегда, а именно ненадежность «split('')». И вот после одного из собеседований, я задумался: «Что же такое я могу передать в строке, что сломает мой способ...?». Ответ пришел очень быстро.

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

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

image

Огонь, работает, супер, но… Подождите ка, с недавних пор мы можем указать цвет для смайла, и что же будет, если мы передадим такой emoji в функцию?
Это фиаско, братан!
image

Вот тут то я и сел в лужу. Если честно, я пару раз предлагал еще на собеседованиях решить эту задачу, в основном, надеясь что мне предложат то решение, которое сможет это сделать — нет, претенденты разводили руками и не могли мне ничем помочь.
Помог случай, ну или спортивный интерес. Со словами «Хочешь задачку со специальной олимпиады?» я отправил ее моему бывшему коллеге. «Ок, к вечеру попробую сделать» — последовал ответ, и я напрягся… «А что если сделает? А что если реально сможет? Он сможет, а я — нет? Так дела не пойдут!» — так подумал я и начал шерстить интернет.
Тут я перейду к теоретической части, которая некоторым из вас может показаться интересной и полезной, а некоторым — повторением пройденного материала.

Что нам нужно знать о Emoji?


Во первых, это — стандарт! Стандарт, который хорошо описан.

Решающим моментом в жизни emoji можно считать день принятия стандарта unicode 8.0 и стандарта emoji 2.0 в нем, тогда и были описаны первые последовательности юникода и последовательности emoji.

Давайте вот тут остановимся чуть подольше и разберем вопрос подробнее.

Согласно первой версии стандарта emoji является представлением одного символа юникода

image

И так далее

Вторая версия стандарта позволяет нам взять несколько симовлов юникода в определенной последовательности, чтобы получить emoji

image

Полный список

Это и есть простые последовательности в emoji, но простые они только потому что есть еще и zwj — последовательности.
ZERO WIDTH JOINER (ZWJ) — соединитель с нулевой шириной, это та ситуация, когда между несколькими emoji вставляется специальный символ юникода ZWJ (200D), который «схлопывает» emoji по обе стороны от него и вот что мы получаем в итоге:
image

Полный список

В последующих стандартах эти последовательности только дополнялись, так что количество комбинаций emoji только росло со временем.

Что ж, с мат частью разобрались, но что же нам делать, чтобы перевернуть строку и при этом сохранить последовательность?

Регулярные выражения.


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

Последовательность может быть составлена по следующей формуле


emoji_sequence :=
  emoji_core_sequence
| emoji_zwj_sequence
| emoji_tag_sequence

# по пунктам 

emoji_core_sequence :=
  emoji_character
| emoji_presentation_sequence
| emoji_keycap_sequence
| emoji_modifier_sequence
| emoji_flag_sequence

emoji_presentation_sequence :=
  emoji_character emoji_presentation_selector
emoji_presentation_selector := \x{FE0F}

emoji_keycap_sequence := [0-9#*] \x{FE0F 20E3}

emoji_modifier_sequence :=
  emoji_modifier_base emoji_modifier
  
emoji_modifier_base := \p{Emoji_Modifier_Base}
emoji_modifier := \p{Emoji_Modifier}
# к этому вернемся чуть позже

emoji_flag_sequence :=
  regional_indicator regional_indicator

regional_indicator := \p{Regional_Indicator}

emoji_zwj_sequence :=
  emoji_zwj_element ( ZWJ emoji_zwj_element )+
  
emoji_zwj_element :=
  emoji_character
| emoji_presentation_sequence
| emoji_modifier_sequence

emoji_tag_sequence := 
    tag_base tag_spec tag_term
    
tag_base := 
  emoji_character
| emoji_modifier_sequence
| emoji_presentation_sequence
tag_spec := [\x{E0020}-\x{E007E}]+
tag_term := \x{E007F}


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

Unicode Categories


В юникоде определены категории, используя которые мы можем в регулярных выражениях находить, например, все заглавные буквы, или, например, все буквы латинского алфавита. Более подробно со списком можно ознакомиться здесь. Что важно для нас: в стандарте определены категории для emoji: {Emoji}, {Emoji_Presentation}, {Emoji_Modifier}, {Emoji_Modifier_Base}, и казалось бы, все хорошо, давайте использовать, но в реализацию ECMAScript они еще не вошли. Точнее — вошла только одна категория — {Emoji}

image

Остальные на данный момент находятся на рассмотрении в tc-39 (stage-2 на момент 10.04.2019).

«Что ж, придется писать регулярку» — подумал и примерно через час мой бывший коллега кидает мне ссылку на гитхаб github.com/mathiasbynens/emoji-regex, ну да, на гитхабе всегда найдется то, что ты только собирался написать… А жаль, но речь не об этом… Библиотека реализует и импортирует регулярное выражение для поиска эмоджи, в принципе то что надо! Наконец то можно попробовать написать реализацию нужной нам функции!



    const emojiRegex = require('emoji-regex');
    const regex = emojiRegex();
    function stringReverse(string) {
        
        let match;
        const emojis = [];
        const separator = `unique_separator_${Math.random()}`;
        const reversedSeparator = [...separator].reverse().join('');
    
        while (match = regex.exec(string)) {
            const emoji = match[0];
            emojis.push(emoji);
        }
    
        return [...string.replace(regex, separator)].reverse().join('').replace(new RegExp(reversedSeparator, 'gm'), () => emojis.pop());
    
    }
    

image

Подводя небольшой итог


Я обожаю задачи со "специальной" олимпиады, они заставляют меня узнавать что-то новое, каждый раз расширяя границы знаний. Я не понимаю людей, которые говорят: «Я не понимаю, зачем нужно знать, что null >= 0? Мне это не пригодится!». Пригодится, 100% пригодится, в тот момент, когда ты будешь выяснять причину того-или иного явления — ты прокачаешь себя, как программиста и станешь лучше. Не лучше кого-то, а лучше себя, который еще пару часов назад не знал, как решить какую-то задачу.

Спасибо за прочтение, всем спасибо, буду рад любым комментариям.

Необходимый постскриптум:

Все сломала буква \u{0415}\u{0308}. Это буква ё, состоящая из 2х символов, оказывается в стандарте юникода есть вариант объединения не только emoji, но и просто символов… Но это — совсем другая история.

UPD: Речь идет не о букве «Ё», а о сочетании 2х символов Юникода u{0415}(Е) и u{0308}("̈), которые идя друг за другом образуют последовательность юникода и мы видим букву «Ё» на экране.
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 414

    +50
    Я бы javascript вынес из тегов в заголовок, иначе когда доходит до задачи, то возникает легкое недоумение…
      +25

      А ещё лёгкое недоумение тут вызывают методы собеседования автора. Приходишь ты такой на собеседование, а тебя спрашивают о знании стандарта, который позволяет поменять зелёную и коричневую какашки из юникода местами. [::-1] тоже, внезапно, не переварачивает html-страницу вверх ногами, не возвращает аргументы javascript-кода по return-value и не делает меня молодым: так может ещё об этом спросить?

        0
        Не стоит. В Ruby метод reverse выдаёт предсказуемый результат с указанной кодировкой.
          0
          В этом случае автор предлагает бороться с проблемами наивного подхода на выбранном стеке.
          Мне кажется, что если эта проблема возникнет в продакшне хотя бы у одного разработчика, появится очередной модуль в npm для корректной манипуляции с Unicode-строками. Или уже есть, но никто не поискал.
        +14
        оказывается в стандарте юникода есть вариант объединения не только emoji, но и просто символов

        Подождите. Я ведь правильно понимаю, что точки над 'ё' — это типичная диакритика, и если ваш алгоритм не работает с 'ё', то он также сломается на «й» (и + ˘) и скорее всего не работает с банальными немецким и французским?
        Неужели эмодзи используются настолько более часто, чем диакритика?
          +2

          Я немного ввел в заблуждение, простите. Речь идет не о букве "Ё", а о сочетании 2х символов Юникода u{0415}(Е) и u{0308}("̈), которые идя друг за другом образуют последовательность юникода и мы видим букву "Ё" на экране.


          \u{0415}\u{0308}' === 'Ё' // false
          
            0
            Попробуйте тест на арабском нет "لا"
              +4
              Лучше смешанный c RLM и LRM, тут и нормализация не поможет :)
                0
                Prelude> no = "لا"
                Prelude> putStrLn $ reverse no
                ال
                Prelude> putStrLn $ reverse $ reverse no
                لا
                Prelude> putStrLn $ reverse $ reverse ("Торт " ++ no ++ " Habr")
                Торт لا Habr
                Prelude> putStrLn  $ reverse ("Торт" ++ no ++ " Habr")
                rbaH ال троТ

                Люблю нормальные, продуманные языки.

                  0

                  Вопрос не а языке, а в библиотеке. С тем же успехом


                  pub fn reverse(input: &str) -> String {
                      UnicodeSegmentation::graphemes(input, true).rev().collect()
                  }
                +3
                Это вполне себе нормальная и, местами, даже типичная буква 'Ё'! Есть платформы, которые нормализуют Unicode к NFC, например, Windows, на них 'Ё' обычно один символ. А есть платформы, которые нормализуют к NFD, например, macOS, там 'Ё' обычно два символа.
                  +3

                  И за это разработчиков макос хочется больно пинать ногами

                    0
                    Хочется, не хочется, вопрос личный. А вот Линуса нашего Торвальдса и компанию обязательно! 21 век на дворе, а файловые системы Linux поддерживают не Unicode, а хрен знает что (набор байтов и граблей):
                    [user@linux ~]$ ls -l /tmp/у*
                    -rw-r--r-- 1 leo staff 31415 апр 11 23:02 /tmp/уй
                    -rw-r--r-- 1 leo staff 271828 апр 11 22:57 /tmp/уй

                    К стати, выбор нормализации NFD, принятый в HFS+ обеспечивает наискорейшее обнаружение ошибок работы с файлами в приложениях. Впрочем и NFС неплох, но не так как в Linux это ж точно.
                      +3
                      Они как раз не занимаются всякой самодеятельностью, а пишут байты как передали.
                        –2
                        И это приводило, приводит и будет приводить к труднообнаружимым глюкам и проблемам с безопасностью. Пока не сделают как все нормальные люди на них клеймо.

                        P.S. Например, habr нормализовал по NFD UTF8 результаты ls и один из этих файлов стал «недоступен». Мало того, ключи ls '-q' или '-b' не изменяют выдачу, т.к. считают значок «кратка» печатным символом.
                          +6
                          Нет уж, кушайте ваши какашки нормализованные сами. Нормализация ещё приемлима в human-to-human интерфейсах, когда машине не нужно интерпретировать текст. В машиночитаемых интерфейсах нормализация неприемлима, ибо она приведёт к ещё более огромной куче проблем и несовместимостей. Как байты записаны — так должны быть и прочитаны, точка. Хумансы для себя должны реализовать удобные средства различения этих байтов — тут не поспоришь.
                            –1
                            Файловая система, либо поддерживает Unicode, либо нет, если поддерживает, то должна обеспечивать нормализацию. Скажем, ZFS (Solaris, FreeBSD) поддерживает, NTFS (Windows) поддерживает, HFS+ поддерживает (macOS).

                            А подход файловых систем Linux — набор байтов, это набор граблей.
                              +2
                              Набор граблей — это когда я записал одни байты, потом прочитал из того же места байты и сравнил с имеющимися у себя. Что дальше? Дальше — исключения, сегфолты или вообще heartbleed, если у нас ФС отнормализовала текст, или всё работает as expected, если не нормализовала.
                                0
                                Куда записал? Имя файла, это не место для записи байт, это «имя файла». Кодируется в URL так, человеку показывается этак и т.п. Плюс обязательная возможность задания образцов поиска, удобных для человека. В половине систем оно вообще нечувствительно к регистру символов, и имеет формы зависящее от языка текущего пользователя.

                                Место для записи байт — бинарный файл.
                                  +1
                                  Ну так пусть инструмент, занимающийся поиском и нормализует (во всех понятиях этого слова)! Зачем здесь ФС-то приплетать?

                                  Имя файла — это просто поле в его метаданных, и в него можно (и иногда нужно) записывать байты. Мне правда нужно привести пример кода, который будет в абсолютно неочевидном месте сегфолтится из-за нормализации?
                                    0

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

                                      0
                                      Затем, что когда ФС нормализует имена файлов, весь (повторяю, весь) софт, работающий с этой ФС, тоже обязан их нормализовать — иначе кровькишки. Если ФС не нормализует — у нас есть выбор. Для вынесения функционала нормализации можно использовать, например, библиотеки.
                                        0
                                        Вот с чего бы «тоже обязан их нормализовать»? Например, с прошлого века большинство систем имеют ФС с именами, которые не зависят от регистра. Как-то без «кровькишки» обходимся.

                                        Так же как и не одно десятилетие работаем с ФС, у которых имена с разной нормализацией Unicode, а так же без нормализации Unicode гарантировано означают один и тот же файл. И тоже без «кровькишки» обходимся.

                                        В чём проблема?
                                          0
                                          Без «кровькишки», говорите? Первое, что вспомнилось (и что очень больно пнуло меня, когда приходилось подрабатывать вебдевом): github.com/jprichardson/node-fs-extra/issues/565

                                          Сейчас ссылок не дам, но точно вам говорю: кровькишки регулярно встречаются. Особенно, когда привык к идеологии «что прочитал — то и записал». Возможно, это деформация линуксоидов какая-то :)
                                            0
                                            Не деформация, детская болезнь, через это многие системы прошли. Мне так кажется.

                                            Встречаются же POSIX системы c EBCDIC именами файлов и locale (z/OS), где даже ASCII — бинарные файлы и невозможные имена. Поэтому инсталляторы Java приложений и jar архивы нужно делать не абы как, а в строгом соответствие со стандартами Java.
                                              +1

                                              Даже если это болезнь, от неё никуда уже не убежишь. Linux прочно закрепился в истории человечества как одна из самых популярных ОС (в широком смысле слова). Менять в нём стандарт сейчас, а не пятнадцать лет назад — уже поздновато. Смена фс на case-insensetive или нормализующую юникод сломает тысячи приложений и миллионы строк кода. Кто будет это чинить?


                                              Для осознания масштабов поломки, можете попробовать сделать C:\ case-sensetive и не-нормализующей.

                                                0
                                                Многие прошли через это. Не проблема, ни сейчас, ни в будущем. Рано ли поздно это неизбежно произойдёт, я так думаю.

                                                «Смена фс на case-insensetive или нормализующую юникод сломает тысячи приложений и миллионы строк кода. Кто будет это чинить?» — linux подсистема Windows является ubuntu и глючит не больше оригинального ubuntu.

                                                Отключить нормализацию на C:\ — тоже без проблем, гарантировано.

                                                P.S.
                                                Ну по популярности, в форме Android — да ;)
                                                  +1
                                                  linux подсистема Windows является ubuntu и глючит не больше оригинального ubuntu.

                                                  Только вот она и не нормализует названия файлов. https://github.com/Microsoft/WSL/issues/1820

                                                  –1
                                                  > Смена фс на case-insensetive или нормализующую юникод сломает тысячи приложений и миллионы строк кода.

                                                  А что, например, с FAT эти миллионы строк до сих пор не умеют? И вы не считаете это проблемой?
                                                    +1
                                                    Не умеют и не считаю. Потому что с FAT даже и Windows 10 «не умеет» (работать с флешками — умеет, встать на FAT — не может).

                                                    В Linux — то же самое.
                                                      0
                                                      Справедливости ради, устанавливаться с FAT-носителя винда умеет.
                                                        0
                                                        Не поддерживать тома FAT больше 32Гб — это не «не умеет», а волевое решение создателей винды. Собственно, до висты винда в 32 Гб помещалась и всё умела, потом просто отключили, ибо нефиг.

                                                        Нет, миллионы строк нерабочего кода и if'чик в инсталляторе — не то же самое.
                                                          +1
                                                          Собственно, до висты винда в 32 Гб помещалась и всё умела, потом просто отключили, ибо нефиг.

                                                          Дело не в объёме ОС, десятка прекрасно умещается на 16ГБ. Дело в активном использовании хард и симлинков, точек соединения, которые не поддерживаются в FAT.
                                                            0
                                                            > десятка прекрасно умещается на 16ГБ.

                                                            Ну как прекрасно… Без ничего, с отключенными гибернацией и файлом подкачки? А если ещё и сжатие включить…
                                                            Ну, несерьезно.

                                                            Раньше вместо симлинков ярлычки были, если помните. Если бы не отказались от FAT — и сейчас бы были. Но да, тоже повод закопать стюардессу.
                                                              0
                                                              Ну, несерьезно.

                                                              Само собой, сейчас меньше 64 ГБ SSD сложно найти.
                                                              Раньше вместо симлинков ярлычки были, если помните.

                                                              Совсем другая сущность.
                                                                0
                                                                > Совсем другая сущность.

                                                                сушность может и другая, а костылили на ней
                                                                  0
                                                                  В предложении отсутствует точка, и оно выглядит не полным. Так и задумывалось?
                                                                    0
                                                                    Отвечал с утюга…
                                                            0
                                                            FAT32, вообще-то бывает аж до 2 терабайт. Windows 98 отлично вам такое создаст, а Windows 10 не создаст (GUI-тулы имеют ограничения), но прочитает. Дело не в объёмах.
                                                              0
                                                              Простите, а какое слово в «волевое решение создателей винды» вам не понятно?
                                            0
                                            Жизнь покажет, думаю и Linux, рано или поздно, тоже придёт к Unicode в файловых системах.

                                            Нет, конечно, можно в ФС ничего не делать, а требовать от всех приложений что б они все идентично нормализовали имена сами ;) Как это сейчас в Linux и происходит, что и позволяет более менее сносно жить. Но такой подход как раз и является тем самым набором граблей ;)

                                            P.S. А ошибки переполнения буферов в неправильных программах они завсегда были и ещё долго будут, причём, что при работе с «вашими» наборами байт, что при работе с нормальными именами Unicode.
                                              +2

                                              Ну тогда объявляем примерно весь софт под Linux "неправильным" — он ведь опирается на предположение, что читает то же самое, что и пишет.


                                              требовать от всех приложений что б они все идентично нормализовали имена сами

                                              Нет, в случае, когда ФС не лезет не в своё дело, каждая софтина может выбрать свой способ нормализации и он будет работать. Да, мы можем создать два "уй" — файла, но зато мы не требуем от каждого приложения заниматься нормализацией всех UTF-строк, которые потенциально могут оказаться в имени файла.

                                                0
                                                Почему «весь софт под Linux неправильный»? Большинство приложений работающих под Linux отлично работают и под Solaris, FreeBSD, macOS и Windows, поскольку они не опираются на неестественное предположение об именах файлов: «что читает то же самое, что и пишет».

                                                Каким боком выше перечисленные системы требуют у каждого приложения заниматься нормализацией? А? По какому имени файл создал, по такому же его и открыть можно ж и т.п. (да, его же можно открыть и по другим именам, эквивалентным данному имени, но почти для всё приложений это не проблема ж)

                                                Некоторое понимание в делах независимости имён файлов от регистра символов или нормализации требуется лишь небольшому числу приложений, например, cvs или svn.
                                                  0
                                                  (да, его же можно открыть и по другим именам, эквивалентным данному имени, но почти для всё приложений это не проблема ж)

                                                  А ещё его можно попытаться поискать в листинге, например. Возникает проблемка, не так ли?

                                                    0
                                                    У большинства приложений наоборот, исчезает проблемка. За исключением, ясен перец, выше поименованных исключений.
                                        0

                                        del, не та ветка

                                          0
                                          NTFS (Windows) поддерживает

                                          Как раз NTFS вообще ничего не поддерживает, кроме
                                          регистронезависимости. Для него имя файла — это UCS-2. Попробовал создать два файла: й.txt и й.txt. Прекрасно создались.


                                          А подход файловых систем Linux — набор байтов, это набор граблей.

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


                                          Так что подход Linux я считаю более адекватным.

                                            0
                                            >Как раз NTFS вообще ничего не поддерживает, кроме
                                            регистронезависимости.
                                            Регистронезависимость это фича Win32 а не NTFS, причем отключаемая фича.
                                              0
                                              Регистронезависимость это фича Win32 а не NTFS, причем отключаемая фича.

                                              Нет. Регистронезависимость — это атрибут директории (кстати, завезли совсем недавно).


                                              В NTFS директория представляется в виде B-TREE, причём ключами этого двоичного дерева являются преобразованные имена файлов (в рассматриваемом случае — преобразованные в lowercase), а чтобы добраться до реального имени файла, нужно лезть в атрибуты записи. Именно возможность быстрого регистронезависимого поиска и позволяет говорить о регистронезависимости NTFS.


                                              P.S. Так-то аболютно любая ФС может быть и регистро-зависимой, и регистро-независимой. Всё зависит от драйвера ФС.

                                                0
                                                Регистронезависимость — это атрибут директории (кстати, завезли совсем недавно).
                                                Атрибут директории завезли недавно, флаг в реестре — скорее всего в прошлом веке. Сейчас на Microsoft документацию для Windows NT и даже Windows XP отыскать сложно, но вот тут говорится, что проблема с Case Sensitivity пофикшены в версях .NET 2.0 (sic!), выпущенных после 2006го — а это значит что поддержка явно старше, раз в 2006м (то есть до выхода Windows Vista) её уже фиксили…
                                                  +1
                                                  Это .net фиксили. Он же не только на винде работает.

                                                  А винду чинили в прошлом году только, тогда и флаги привезли все, и ключи.
                                                    0
                                                    Это .net фиксили. Он же не только на винде работает.
                                                    Как прекрасен этот мир, посмотри… поколение «не рефлексирующих, а распространяющих», похоже, окончательно победило. С учётом того, что вас ещё и плюсуют.

                                                    Это у вас «не на винде реестр вдруг появился? С ключом

                                                    HKLM\SYSTEM\CurrentControlSet\Control\Session Manager\kernel\

                                                    dword:ObCaseInsensitive?

                                                    Это где же вы такое нашли, интересно? И где вы в 2006м году нашли .NET не под Windows?

                                                    Нет, всё это точно было в Windows XP, не удивлюсь если и в Windows NT 3.1 тоже всё было — просто проверить негде.
                                                      0
                                                      Надо просто понимать разницу между документированными функциями ОС, и какими-то флажками в реестре. Драйвер ntfs много что умеет, но кроме этого драйвера в винде есть ещё ядро, слой апи для приложений, и сами приложения и их пользователи тоже — часть экосистемы винды. Так вот в винде, как экосистеме, регистрозависимые имена файлов появились в прошлом году. Это потребовало и изменений в Win32, и доработки приложений, и обучения пользователей и много чего ещё.

                                                      А в 2003 году был всего лишь недокументированный флаг в реестре, который техподдержка включала для каких-то специфических кейсов отдельных пользователей. Ну и код в драйвере. Но там очень много очень разного кода, не все из этого «винда поддерживает»
                                                        +1
                                                        Надо просто понимать разницу между документированными функциями ОС, и какими-то флажками в реестре.
                                                        А какая разница? Где сегодня, сейчас, в Windows 10 большая кнопка, которая включает/выключает регистрозависимость? Чем команда в PowerShell «интуитивнее» ключа в реестре?

                                                        Так вот в винде, как экосистеме, регистрозависимые имена файлов появились в прошлом году.
                                                        В винде, как в экосистеме, всё это появилось больше четверти века века назад — в Windows NT 3.1. Где и флажок FILE_FLAG_POSIX_SEMANTICS был (это, блин, вообще первый «расширенный» флаг, который в CreateFile появился) и регистронезависимость была и даже POSIX-подсистема была!

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

                                                        Но там очень много очень разного кода, не все из этого «винда поддерживает»
                                                        Конкретно регистронезависимость она поддерживала весьма прилично ибо ей нужно было пройти POSIX-сертификацию. Ибо в те времена в госучреждениях разрешалось использовать только POSIX-совместимые OS.
                                                          0
                                                          Разница в уровне поддержки и документации, раньше это «есть какой-то флажок, но если что-то сломается, то не обижайся». Как раз для вот таких любителей посикса.

                                                          Сейчас это поддерживается во всех стандартных сценариях, и насколько помню, в RS5 они хотели вообще включать это по дефолту в новых установках.
                                                            0
                                                            Дык оно и изначально во всех сценариях поддерживалось. Ограничения появились только в Windows 2000 — до этого и вариантов-то не было: каждая программа могла сама решать будет она поддерживать регистронезависимость или нет.

                                                            Флажок, когда появился, позволил оптицонально эту поддержку отключать — отменяя флаг FILE_FLAG_POSIX_SEMANTICS, который, ещё раз повторяю, был там с самой первой версии Windows NT.
                                                        0
                                                        Ах да, инсталлятор дотнета, похоже, как раз ломал те самые специфические кейсы отдельных пользователей. Видимо, они пользовались не только виндой и им эта регистрозависимость была нужна. Вот инсталлятор и починили в 2006 году.
                                                          0
                                                          На самом деле это была классическая схема bait-n-switch, за которую у Microsoft'а много денег отсудили.

                                                          Изначально поставляя Windows NT как POSIX-совместимую систему начиная с Windows 2000 Microsoft начал делать попытки заставить всех отказаться от POSIX и перейти исключительно на Win32 API. Извините, но инсталлятор не может «случайно» залезть в реестр и выключить там регистронезависимость. Этот код кто-то должен был в него целенаправленно добавить. Совершенно случайно посреди инсталлятора вполне конкретная строка в 50 символов длиной не возникает.

                                                          Но с учётом того, что Microsoft и так в судах трепали в то время изрядно — признать это Microsoft не мог и потому пришлось делать вид, что «ой — да мы ошиблись просто, никто ничего „такого“ и не хотел».

                                                          Но окончательный отказ от этих попыток — да случился не так давно.
                                                            0
                                                            Свечку не держал, но это не строка кода, а запись в бд инсталлятора. Хз что они там пытались починить. Может там какой-то бинарь переименовали, а пересобирать все зависимые модули не захотели, релиз скоро, размер патча ограничен, ещё там что — вот и воткнули костыль.
                                +3
                                Нормализацию сделайте перед реверсом. Должно помочь.
                                  0

                                  Тогда reverse(reverse(s)) !== s

                                    +1
                                    Это нормально. Перед сравнением двух юникодных строк их необходимо нормализовывать.
                                  +7
                                  R̸̩͔̫̠̪̠̪ͤͬ͜I͍̱͉̝̐ͫ̾̅͂̒ͥ͌͟D̵̴̘͙̤͖̪̖̭̲ͦD͔̘̼̫̬͓ͥ̈́̑̂Ľ͇͙͙̠͕ͪ̏̈́E̢̡̡̫̘̔̋͂ ̛̳͚͈̰͙̲̀ͩM̗̘̩̣͉͇ͬ̔ͨͥ̎̕E̛̟̭͖͈̩̐ͩ͗ͩ̎̕ ͖͔̠̳́ͭ͆̏ͪṬ̢͓͈̞͛̕Ḩ̡̣͔͖͎͚̤̻ͥ͒I̓̏̏̈҉̵̳̞̠͍̯S͔̬̙̱̱̝͂ͯ̈́͐̂͜
                                0
                                Да, на macOS на имени файла 'уй' алгоритм тоже точно сломается. Для Unix/Linux/Windows вероятность поломки невелика есть, если только не использовать unorm, `iconv -t utf-8-mac' или иных явных средств нормализации Unicode.
                                +91
                                Внезапно, оказывается, если в строке левая кодировка, то нужно обрабатывать эту левую кодировку.
                                ВОТ ЭТО ПОВОРОТ.
                                Да, реверс строки сломается если в строке не строка.И?

                                А еще меня как Сипипишника ввело в недоумение вот это утверждение:
                                самым оптимальным для себя я долго считал такое решение:
                                const strReverse = str => str.split('').reverse().join('');

                                split и join — это эффективно? Эффективнее чем тупо перебрать половину строки и сплитнуть руками с другой половиной? Ладно, нет возможности модифицировать строку. Но что мешает без сплита сразу писать в массив и его конвертировать в строку? Разве это не будет эффективнее?
                                Я бы охерел, если бы на вакансию С++ программиста кто-то для реверса строки сначала её в отдельный список/массив конвертировал.
                                Если в вебе это норма — не удивительно что у нас всё так плохо в браузерах.
                                Если я не прав в своих суждения — расскажите пожалуйста почему автор считает такой подход правильным и наиболее эффективным.
                                  +19

                                  Там еще и эффективными считаются цепочки из операций filter/map над массивами, которые порождают промежуточные массивы.

                                    0
                                    Разве эти методы не работают с итераторами, как в нормальных языках?
                                      +1
                                      Не работают, это filter/map/и т.д. чисто методы массивов (ну и у некоторых массивоподобных объектов есть forEach).
                                      Если нужен filter/map для итераторов, то ищем реализацию на стороне.
                                        0
                                        Итераторы-то совсем недавно завезли, а стандартные методы были всегда.
                                          +1

                                          filter, map завезли в ES5, итераторы — в ES6.

                                            0
                                            Пожалуй я преувеличил насчет «всегда», но ES5 был еще в 2009, а ES6 только в 2015.
                                        +2

                                        Я бы уточнил, что эффективными в разрезе «производительность — стоимость поддержки».

                                          +2
                                          Вообще, насколько мне известно, трюк с
                                          .split().reverse().join()
                                          — это что-то вроде шутки в рамках контекста такой задачи.
                                          Удивительно, что автор посчитал этот ответ зачетным.
                                            +1
                                            ну и потом автор рассказывает что _В_ТОМ_ЯЗЫКЕ_ split() вообщем то неправильно сплитит…
                                          +28
                                          Автор не использовал слово «эффективно». Автор использовал слово «оптимально» без указания критерия оптимальности. Возьмусь предположить, что имелось ввиду «оптимальное по размеру кода и очевидности».
                                            +8
                                            ну так можно дойти до того, что у эффективности тоже не указаны критерии.
                                            эффективно по количеству символов в решении? по количеству затраченного времени? по стоимости часа программиста способного это написать?
                                            Так что ваш довод не принимается. Если заменить в моем тексте слово «эффективно» на «оптимально» суть ни на грамм не поменяется.
                                              +12
                                              split и join — это эффективно? Эффективнее чем тупо перебрать половину строки и сплитнуть руками с другой половиной?


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

                                              Автор: вот короткое решение
                                              Вы: разве это быстрое решение?
                                                +5
                                                Разве короткость — это оптимальный критерий для оценки тестового задания?
                                                  +19
                                                  В данном случае, java script не предназначен для поиска оптимального решения задачи реверса строк по количеству необходимых операций и размера памяти, а просто демонстрирует способность кандидата использовать стандартные вещи из JS.
                                                  В питоне реверс массива выглядит еще короче, что-то типа myarray[::-1], как там «под капотом устроено» нужно смотреть дополнительно.
                                                  А вот в c++, данная задача хороший индикатор на некоторую адекватность разработчика. Ну просто не всегда нужно мыслить терминами одного инструмента при использовании другого, тем более они предназначены для разных задач.
                                                    +17
                                                    А вам не кажется что такой подход является причиной того, что веб такое днище в плане потребления памяти и производительности?
                                                    Я часто слышу что JS гавно. Но здесь я вижу не проблему языка, а проблему выбора решения внутри языка.
                                                      +1
                                                      что JS гавно

                                                      Смотря с какой точки зрения.
                                                      Производительность, потребление памяти, отсутствие нормальной мультипоточности (да я знаю про webworkers) по сравнению с более низкоуровневыми языками — да я тут согласен.
                                                      Но, если смотреть на порог вхождения, умение упрощать некоторые оплошности, отсутствие зубодробительных практик из того же С++ (я про указатели, наследование, темплейты, виртуальные деструкторы и т.д.), он почти идеальный кандидат для массового применения в действительно областях, где требуется большое количество разработчиков. На мой взгляд очевидно, что сайтов бизнесу можно куда больше и быстрее написать на javascript, чем на c++.
                                                        –17
                                                        C++ в разы проще чем весь этот треш типа пизонов перлов джсов и т.д.
                                                        Что написал — то получил. Любое действие можно разобрать до минимальных шагов, а не спотыкаться. А стандартные библиотеки подняли «низкоуровневость» С++ до «среднеуровнего» благодаря своим алгоритмам и контейнерам.

                                                        В то же время, я садясь за питон, чуть волосы на голове не вырвал по началу. Он мне понравился, но на сколько же он сложен. По переменной не понятно что она такое. Каждый объект может иметь внутри произвольные переменные. Нет ни удобных указателей что бы изменить внутри функции значение аргумента, или что бы хотя бы не копировать этот аргумент каждый раз.
                                                        Деструкторы, наследование, указатели, вот это все есть либо в неявном виде (нужно понимать как работают эти ссылко-указатели в языке) до явного когда деструктор это метод «Деинит» который закрывает соединение корректно, или еще-что то.
                                                        В итоге все тоже самое, только в куче.

                                                        Хоть и быстрее писать после изучения, не спорю, но «неопределенность» модных в бизнесе языков сильно повышает порог вхождения в программирование в целом
                                                          +3
                                                          C++ в разы проще чем весь этот треш типа пизонов перлов джсов и т.д.

                                                          Это вопрос привычки. Для того кто всю жизнь писал на С++ кажется что он проще, для того кто писал на javascript чтo javascript.
                                                          А возьмите человека который пишет на java или C#, так для него что С++, что javascript это неудобный адовый ад.
                                                            +2
                                                            Я пишу на жабе, и вы частично неправы:
                                                            С++ для меня ад, а скрипты очень даже хороши…
                                                            +11
                                                            удобных указателей что бы изменить внутри функции значение аргумента

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


                                                            С++ не проще. Он сложнее. Писать на нем дольше (вы и сами с этим согласны). Да, он даёт бОльший контроль за некоторыми вещами, но этот контроль часто не нужен. Вы же не контролируете из С++ переключение вентилей напрямую? Абстракции — это крайне полезное изобретение человечества.

                                                              +1
                                                              Простые объекты не передаются по ссылке, если мы про питон. Кроме того, сделав внутри функции objectExt=objectNew вы принимаемый аргумент не измените и вообще потеряете, по сути, из виду.

                                                              Как не проще, если С++ предлагает вам почти тот же уровень абстракций, как и «простые» языки, и, если нужно позволяет вам опуститься на уровень ниже. Разве не это простота?
                                                              Для того что бы писать на «простом» языке больше чем HW, нужно все так же понимать как он внутри работает и использовать все теже фичи, что вы будете использовать и в С++. Нужно так же знать что такое ссылка, что такое указатель, без этого никуда не уедешь. Нужно понимать чем List=List+AnotherList (опять питон) будет отличаться от list.extend(AnotherList). Понимать как в зависимости от контекекста происходит каст одного типа к другому, и как будут операторы работать (JS?). Как происходит наследование, что за self. такой вообще. И многое другое.
                                                              Не нужно исключать работу с классами и объектами которые зависят от их контекста. Таже библиотека «таблиц» Pandas питоновская. Что бы понять в каком виде она приходит тебе, нужно взять все что происходит с ней до этого, причем я сейчас про структуру (колонки их типы, их названия), а не значения. В С++, если мне не нужна супер пупер гибкость на шаблонах, любой новичек сможет ткнув в структуру понять как она выглядит и какие типы содержит, и при написании кода IDE никогда не позволит ему забыть что там есть благодаря подсказкам.
                                                              В С++ все с этим проще, все работает намного более явно. А ногу отстрелить не в пример сложнее, достаточно забыть про с98 и перейти на сxx14+ с shared_ptr.

                                                              >Писать на нем дольше (вы и сами с этим согласны).
                                                              Да, и не так гибко (если вы не гуру шаблонов). Однако не сложнее точно.
                                                                +2
                                                                Кроме того, сделав внутри функции objectExt=objectNew вы принимаемый аргумент не измените и вообще потеряете

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


                                                                если С++ предлагает вам почти тот же уровень абстракций

                                                                Почему под веб пишут на php и питоне, если С++ по вашим словам не хуже и гибче? Библиотеки? Половина их написана на си, так почему их пишут на си для питона и php, а не для самого си?


                                                                Я не буду предполагать, что разработчики идиоты или сумасшедшие и просто не догадываются, что си++ для их целей лучше. Наоборот, разработчики в среднем обладают высоким интеллектом. И если они (и я в том числе) используют php и питон для веба, значит есть преимущества.


                                                                И они на самом деле есть. Мне абсолютно точно не нужно прямое управление памятью, когда я делаю какой-то веб-сервис. Отсутствие такого управления — это преимущество, ускоряющее разработку и облегчающее поддержку старого кода. Потому что обязательно найдется кто-то, кто захочет памятью по-управлять. И если он не сможет этого сделать, значит он не подложит мне мину замедленного действия.

                                                                  0
                                                                  Это крайне правильно. В идеальном мире объект, передаваемый в качестве аргумента, вообще нельзя поменять

                                                                  Что, простите? Откуда это странное утверждение появилось?

                                                                  Почему под веб пишут на php и питоне, если С++ по вашим словам не хуже и гибче?

                                                                  Покажите пожалуйста где я написал что С++ гибче? Я помойму такого не говорил, а наоборот даже утверждал обратное?
                                                                  А пишется потому что «простые» языки дают возможность писать гибче и быстрее.

                                                                  Хочу обратить внимание, мы с вами изначально говорили не о скорости и гибкости, а о простоте. Не нужно смещать фокус, о том что быстрее будет накалякать на динамическом интерпретируемом языке я не спорю.
                                                                    +1
                                                                    Откуда это странное утверждение появилось?

                                                                    Не все вещи, которые вам кажутся странными, на самом деле такими являются. Чистые функции считаются хорошей практикой. А грязные — ведут к неожиданным багам.


                                                                    Изменение аргумента функции — это побочный эффект. Такая функция не является чистой.


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


                                                                    Как пример — в JavaScript есть линтер, ESLint. При попытке изменить аргумент функции он выдает предупреждение.

                                                                      –3
                                                                      А какую-то аргументацию к этому, извините, бреду, можно услышать?
                                                                      Очень многими програмистами считается хорошей практикой «тяп-ляп и в продакшен», поэтому это очень слабый аргумент.
                                                                        +2

                                                                        Просьба без истерик. Если у вас есть доводы, что чистые функции "бред", буду рад их услышать. Забавно, что вы не сказали "чистые функции — плохо", вы сказали "бред". Бессмысленное, вздорное, несвязное. Вместо того, что бы загуглить "что такое чистые функции", вы сразу назвали их бессмысленным вздором. Очень забавно.


                                                                        Если вам нужна аргументация к тезисам, скажите к каким. "Функция с побочными аргументами не считается чистой" — это нужно как-то аргументировать или вы этот "бред" просто в Википедии проверите?

                                                                          –1
                                                                          Эм?
                                                                          У вас с чтением большие проблемы. Мы говорили о простоте, вы свели к скорости написания кода. И сейчас, опять, вы совсем другое читаете, ведь очевидно что не существование термина чистые функции — бред, термина который даже в институтах преподают, а теория о превосходстве использования только чистых функций.
                                                                          И вы первый об этом написали, о том что писать на чистых функциях лучше, поэтому и флаг вам в руки в первом шаге аргументации.
                                                                            0

                                                                            Совсем другое дело. Вы просто не согласны с тем, что чистые функции — хорошо. Ни о каком "бреде" речь уже не идёт.


                                                                            Вот только не я высказал этот тезис первым. Аргументацию вы можете легко нагуглить, какой смысл в том, что бы я её сюда копировал? Как вы сами сказали, чистые функции даже в институте преподают, значит и их пользу рассказывают.


                                                                            Пересказывать не вижу смысла, зачем это мне и вам? Тратить время на набор текста. Если вам хочется использовать чистые функции по-реже и постоянно менять аргументы функций, если вы любите побочные эффекты (предположим) — это полностью ваше дело. И тех, для кого вы пишете код.


                                                                            А поймать меня на слове "только" не получится. У нас же не идеальный мир, поэтому хаскель никогда не станет самым популярным языком.

                                                                              –2
                                                                              Почему же не идет речи, если «чистые функции есть хорошо» — бред как он есть?
                                                                              Это крайне правильно. В идеальном мире объект, передаваемый в качестве аргумента, вообще нельзя поменять, это не сделано просто по соображениям производительности, а не как фича.

                                                                              Это написали вы. А теперь отправляете в гугл. Удобно.

                                                                              К слову, идеальный мир, в котором нельзя менять аргумент и будет мир в котором «только» чистые функции. Так что, поймал, хехе.
                                                                                0
                                                                                ЕМНИП, в Аде были только чистые функции и «грязные» процедуры.
                                                                                  +2
                                                                                  Так что, поймал, хехе.

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


                                                                                  бред как он есть?

                                                                                  Удачи вам с таким уровнем ведения диалога. Назовите любой тезис оппонента "бредом" и вам не придется приводить своих доводов. Очень удобно, всегда в выигрыше. Но интереса в этом нет.

                                                                                    0
                                                                                    В нашем мире грязные функции приемлимы, иногда их нельзя избежать.

                                                                                    На чистых функциональных языках программиста избавляют от этой мучительной муки — грязные функции там только в рантайме языка.

                                                                0
                                                                Ну да, написал сегфолт — получил сегфолт
                                                              +19
                                                              Если вы хороший разработчик, вы оптимизируете правильные места.

                                                              Это поиск баланса между читаемостью и эффективностью. Если вам нужно реверснуть небольшую строку, то сплит-реверс-джоин работает так же быстро, как и что угодно ещё — там разница на уровне пары миллисекунд. При этом смысл кода понимается беглым взглядом, меньше, чем за секунду. Давайте напишем цикл:
                                                              var str = '12345';
                                                              var reversed = '';
                                                              var l = str.length;
                                                              while(l--){
                                                               reversed += str[l];
                                                              }
                                                              

                                                              — и чтобы понять, что делает этот код, понадобится секунд 5.

                                                              И так везде. Если вы пишете очень критичное место (вроде сравнения v-dom в таблице на миллион пунктов), то да, его нужно оптимизировать всеми силами и средствами, потому что какая–нибудь мелочь может привести к разницы в полсекунды. Если разницы нет, то и смысла нет — выбирайте, что читаемее.
                                                                –20
                                                                Не работает этот так. Ну вот просто не работает. Если вы используете неэффективный алгоритм и медленно работающий код — то результатом будет новый GMail. Жрущий на порядок (если не на два) больше ресурсов, чем версия 10-15 летней давности и не дающий при этом никаких новых возможностей!
                                                                  +30
                                                                  Если у вас есть массив из 4 элементов, и вы по кнопке его сортируете, то сортируйте хоть перебором, 24 перестановки комп переберёт почти так же быстро, как и отсортирует пузырьком. Место не критичное.

                                                                  Медленно работающий гмейл — это результат того, что плохой код в критичном месте, понимаете? Критичные места — это то, что нужно оптимизировать.
                                                                    –9
                                                                    Критичные места — это то, что нужно оптимизировать.
                                                                    Если вы прочитаете соответствующую статью, то обнаружите, что… миф таки остался мифом. Судя по тому, что что там осталась куча метрик — критичные места там диагностировались и оптимизировались. Результат — тормоза и дикое потребление памяти.

                                                                    Медленно работающий гмейл — это результат того, что плохой код в критичном месте, понимаете?
                                                                    Нет — не понимаю. Более того — не понимаю категорически. Я ещё ни разу не видел ситуации, когда «феншуйный» год, который писали думая об «идеоматичности», «гибкости» и прочим разным баззвордам (но не об эффективности) после оптимизации работал бы хотя сравнимо по скорости с кодом, который писали изначально думая-таки об эффективности.

                                                                    Если у вас есть массив из 4 элементов, и вы по кнопке его сортируете, то сортируйте хоть перебором, 24 перестановки комп переберёт почти так же быстро, как и отсортирует пузырьком. Место не критичное.
                                                                    Рассуждение кажется разумным — но он в корне неверно. Ибо предполагает, что вы знаете заранее что там будет 4 элемента. А их там может оказаться, в результате работы какого-нибудь «дезигнера» и 44 и 444444 — ничего заранее предскзать нельзя, если не контролировать что вы делаете на всех этапах.

                                                                    Я с этим сталкивался неоднократно: когда меня просят что-то оптимизировать и я разрушаю «весь феншуй» путём превращения кода из «торта Наполеон» в 100500 слоёв в что-то гораздо менее «феншуйное» — то у меня часто спрашивают о том, как я собираюсь это профайлить и откуда у меня будет вылезать статистика… и вы знаете… я обычно вообще не собираюсь об этом думать. Того факта, что версия «не по феншую» работает в 3-5-10 раз быстрее оптимизированной в «критических местах» «феншуйной» версии — обычно оказывается достаточно.

                                                                    P.S. Это, кстати, не значит, что я совсем никогда не пользуюсь профайлером. Это было бы глупо. Но важно всегда понимать заранее — где у вас в программе неэффективности… тогда профайлер подскажет вам — какие из них реально влияют на код, а какие — нет. Если же вы списка неэффективностей не имеете — можете хоть упрофайлится, результатом будет GMail.
                                                                      +2

                                                                      Например, есть задача — отсортировать массив интерфейсов устройства USB при обработке события втыкания этого устройства. Вы туда что, квиксорт бы стали пихать?

                                                                        0
                                                                        В этом случае я бы не соритировку писал бы, а пихал бы уже в отортированном порядке.
                                                                        И вообще может задача найти первый отсортированный, тогда можно не доводить сортировку до конца, а сделать сортировку кучей которая после первого этапа имеет «наверху» самый большой элемент.
                                                                          +1
                                                                          И вообще может задача найти первый отсортированный, тогда можно не доводить сортировку до конца, а сделать сортировку кучей которая после первого этапа имеет «наверху» самый большой элемент.

                                                                          Это вы так поиск минимального или максимального элемента бы так делали?

                                                                            0
                                                                            Конечно нет))) Сортировку кучей хорошо применять, когда не нужно сортировать все, а нужно скажем первые 10 самых маленьких/больших из большого массива данных, т.е. сортировать каждый раз полностью массив данных не требуется, в этом случае сортировка кучей хороша и это будет работать быстрее чем сортировать каждый раз той же быстрой соритровкой.
                                                                            Если смысл именно найти наибольший, то естественно нет смысла. Наиболее разумно либо класть уже в отсортированном порядке либо класть в конец и вызывать сортировку кучей, если предваритель но массив уже был кучей, то установка нового элемента в нужное место кучи будет быстрой. короче это хороший способ если периодически требуется выдавать несколько самых больших/маленьких элементов, переодически вставляя значения.
                                                                            0
                                                                            На входе — несортированный список интерфейсов, прилетающий из другой либы. Надо выводить отсортированный список, плюс требуется последовательно пройтись по интерфейсам, найдя первый, удовлетворяющий определенным критериям.
                                                                              0
                                                                              В изначальном вопросе не было сообщения, что массив прилетает из вне.

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

                                                                              Можно в принципе передалать архитектуру, чтобы при подключении/отключени устройства к нам прилетало это событие и мы внутри себя уже хранили бы отсортированный списк, тогда сортировку проводить каждый раз было бы не надо и надо было бы выбрать по критерию и вернуть уже хранимый нами отсортированный список.
                                                                            0
                                                                            Почему нет? Правильно написанный квиксорт для небольших размеров подмассивов использует сортировку вставками.
                                                                            Как результат у нас будут эффективно сортироваться как маленькие массивы, так и большие.
                                                                              0
                                                                              Тогда это уже не квиксорт, а какой то гибридный вариант сортировки. И да, он будет больше и сложнее каждого из этих алгоритмов. Я уж не говорю о том, что для однократной сортировки очень маленьких размеров данных вообще пофиг какой алгоритм выбрать.
                                                                                0
                                                                                Почти во всех библиотеках он именно так и реализован для того, чтобы убыстрить его. Вызывая его совершенно не важно, что он гибридный. Это уже давно так. Нужен чистый — пиши свой, но зачем? Мне, например, бетчера нравится из-за того, что его отлично можно распаралелить.
                                                                                0
                                                                                Зачем тратить время на реализацию квиксорта для десятка записей, которые сортируются один раз при втыкании устройства USB? Какой в этом смысл? Сделать определение устройства не 15 секунд, а 14.999999?

                                                                                  +1
                                                                                  А зачем его тратить? Квиксорт есть в стандартной либе многих языков. В той же жабе как раз таки со встроенной сортировкой вставками. Вот если его нету, тогда другой вопрос. Хотя опять же, простой вариант квиксорта пишется примерно за столько же, за сколько и сортировка вставками/выбором/пузырьком. Может на 5 минут дольше. И это если лень залезть в гугл и найти имплементацию например того же Седжвика.
                                                                              +1
                                                                              Всё это очень здорово, но представте что «не феншуйно, но зато быстро» пишете не Вы, а вчерашний студент, который старается так, как может. Потом пару лет этот код поддерживает команда из нескольких человек с разным уровнем навыков — джависты, эс-ку-эльщики, заскучавший скрам-мастер, который решил что ему между многочисленными митингами неплохо бы и в программировании поупражняться… При этом на команду давят со сроками, поэтому обновлять документацию времени нет, а юнит-тесты поддерживаются лишь так, чтоб те своими падениями не мешали бы деплою.

                                                                              После чего этот код переходит Вам и Вам надо с ним работать. При этом времени «это всё выкинуть и переписать с нуля» Вам абсолютно точно не дадут, потому что код работает и приносит бизнесу деньги. Ну как, нравиться перспектива, или Вы бы предпочли, что бы код изначально писался бы пусть и не так быстро, но зато «феншуйно», давая возможность даже средним специалистам найти узкие места и оптимизировать только их?
                                                                                +2
                                                                                О, могу рассказать, как пишут студенты. У нас это хорошо видно.

                                                                                Начну с того, что у моего руководства есть идея фикс: «сейчас мы наймем новых людей и они сделают все хорошо». Совершенно восхитительная идея, что набивший шишки на предыдущих проектах, опытный работник заведомо хуже любого новичка. Я сам, кстати, так пришел, и был в восторге от возможности разрабатывать архитектуру, делать все так, как хочется, без оглядки на кого бы то ни было. У меня тогда хотя бы лет пять опыта разработки было.

                                                                                Пару лет назад началась очередная итерация «сделаем все по-новому». Пришли студенты (прям реально студенты, они тогда еще доучивались) и понеслось. Нет, ребята очень умные, вот только опыта никакого. Запилили структуру данных, в которой и десятка тысячи записей никогда не будет. Ни о какой высокой нагрузке речи не идет — по сути это конфиг устройства, обращения к которому достаточно редки. Умудрились впихнуть туда самописные би-деревья и хэш-таблицы. И это не смотря на то, что сам конфиг хранится в JSON, а используемая либа — jansson — сама по себе (сюрприз!) основана на хэш-таблицах. Нет, надо показать, что мы не лыком шиты и знаем алгоритмы.
                                                                                И такое везде — хитрые операции с указателями, огромные макросы, трюки с gcc. Такие практики имеют право на жизнь, но там, где они необходимы, а не по всему коду, который становится абсолютно нечитаемым.
                                                                                Самое смешное обнаружилось, когда эта разработка начала внедряться, и с ней пришлось работать остальным. Ребята не сделали НИЧЕГО для синхронизации доступа из разных процессов! После того, как на это им указали, сначала вяло отнекивались, что это должно работать как-то «само по себе», а потом все-таки запилили один big fucking lock на весь конфиг. На предложение сделать ниспадающую блокировку, замораживающую только ветки, растущие из нужной ноды, сказали, что это сложно и долго делать. Вот так: оптимизировали би-деревьями, а потом все процессы ждут, пока один закончит свою работу.

                                                                                Что имеем в результате. Косую архитектуру, никакую мотивацию у старых работников и постоянное переписывание кода. Зато за это время мы слышали много умных слов про «чистый код» (в реальности весьма кривой), про крутость датамодели (в реальности очень костыльная реализация в JSON) и про оптимизации (в реальности хэш-таблицы на списке из ТРЕХ команд).
                                                                                0

                                                                                Похоже, вы разбираете говнокод посредственных программистов. Это нормально, потому что посредственных больше, чем хороших. Но вы ради интереса разберите хороший проект на javascript. Vue.js, например (можете выбрать любой, какой хотите). Ускорить, удалив 80% возможностей вы, без сомнения, сможете. Но сможете ли ускорить, оставив функционал?

                                                                                  0
                                                                                  Ускорить, удалив 80% возможностей вы, без сомнения, сможете. Но сможете ли ускорить, оставив функционал?
                                                                                  Смотря что понимать под «функционалом». Если мы о бизнес-требованиях — то да, легко. А вот если о метаниях дезигнеров или всякого рода баззвордом — нет, конечно. И не нужно.
                                                                                    +1

                                                                                    Хорошо. То есть если я хочу какие-то дизайнерские особенности, мой дизайнер нарисовал и я хочу заплатить денег, что бы это реализовать, вы не можете и денег не возьмёте. Скажете "не нужно, не делайте так".


                                                                                    А люди, которые делают 20 слоев абстракций — сделают. Что ж, это полностью объясняет, почему у софта, который всё же взяли и сделали, так много слоев, не правда ли?


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

                                                                                +1
                                                                                Медленно работающий гмейл — это результат того, что плохой код в критичном месте, понимаете? Критичные места — это то, что нужно оптимизировать.


                                                                                Я думаю, там вопрос не столько в качестве кода, сколько в количестве. Не даром он там 600мб памяти занимает.
                                                                                0
                                                                                Почему гмайл не даёт новых возможностей? Новые возможности у товарища Майора и Гугла для впихивания рекламы
                                                                                  0

                                                                                  Он даёт очень много возможностей по сравнению, например, с аутлуком. Не знаю, на чем написан аутлук, но точно не на JavaScript.


                                                                                  Только не спрашивайте, каких. Просто посмотрите, сколько людей пользуются Gmail. Значит у него есть какое-то преимущество перед аутлук. Преимущество именно для них.

                                                                                    0
                                                                                    Не знаю, на чем написан аутлук, но точно не на JavaScript.

                                                                                    Тот аутлук, который outlook.office.com? Судя по стилю кода, он изначально написан на ES5, а затем просто минифицирован каждый файл в отдельности. Судя по тому, что в коде используется Microsoft AJAX Library, это часть обычного проекта ASP.NET. То есть, там даже TypeScript в основной массе нет.

                                                                                      +1

                                                                                      Я про тот, который вообще не в браузере.

                                                                                      0
                                                                                      Эмм. Очевидное преимущество gmail'а перед outlook'ом — он бесплатный (ну, на поверхности). В плане фич и скорости работы gmail'у до него далеко, но я не вижу причин вообще сравнивать бесплатное веб-приложение и дорогой офисный продукт.
                                                                                      Плюс многие пользуются gmail'ом именно как почтовой службой, а его сверхтяжелый интерфейс им даром не нужен. И, сюрприз, есть люди, которые читают почту своего gmail-ящика через outlook.
                                                                                        –1

                                                                                        Кому-то не нужен. Кому-то нужен. Вы правильно описали, что у разных людей разные причины пользоваться. А утверждение выше, что "gmail" не даёт новых возможностей, не верно. Раз пользуются, значит им даёт. Благо выбор огромен.

                                                                                          0
                                                                                          Раз пользуются, значит им даёт.
                                                                                          Пользуются потому что и раньше пользовались.

                                                                                          А утверждение выше, что «gmail» не даёт новых возможностей, не верно.
                                                                                          Можете назвать хоть одну? Ещё раз: я не про GMail 2004го года (там как раз требований к ресурсам было не так много, а новых фич — много), а про GMail 2018го из анекдота «зачем ты Ролекс за миллион купил, вот там за углом такой же за пять».
                                                                                            0

                                                                                            Могу, конечно. Группировка писем по категориям/полезности. Вы скажете, что это можно было реализовать и в старом gmail? В теории — да, можно. На практике разработчики быстрого кода сказали, что "это не нужно" и пришлось gmail перепилить силами любителей абстракций. А что делать? Отказываться от реализации фичи, потому что разработчик опять говорит "не нужно"? Это хуже, чем медленный софт, приходится мириться с тормозами.


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

                                                                                              0
                                                                                              Группировка писем по категориям/полезности.
                                                                                              Вот только эта группировака уже была в старом GMail. Она не в 2018м году появилась.

                                                                                              Просто представьте себя на месте владельца софта.
                                                                                              Представляю. Пользователи уже начали уходить в IMAP и прочее. А со временем — могут и к другим провайдерам уйти.
                                                                                                0

                                                                                                Видимо я не смог нормально описать, что я имею ввиду. Та группировка, о которой я веду речь, появилась года два назад.


                                                                                                Впрочем, не существенно. У вас, видимо, есть другое объяснение, почему gmail сделан так. Если я вас верно понял, это потому что там одни идиоты и любители специально делать плохо. Что-то я сомневаюсь, что это на самом деле так, но дело ваше.

                                                                                                  +1
                                                                                                  Та группировка, о которой я веду речь, появилась года два назад.
                                                                                                  А я говорю о новом интерфейсе, появившемся в прошлом году.

                                                                                                  Если я вас верно понял, это потому что там одни идиоты и любители специально делать плохо.
                                                                                                  Ни в коем случае. Этот случай уже разбирали. Просто за 15 лет с момента выхода первой версии GMail изменилась культура внутри компании.

                                                                                                  15 лет назад, когда выходила первая версия GMail, её разрабатывали и оценивали инженеры. Сегодня — это делают, как и везде, «эффективные манагеры». Которые ценят «запуски» (launch) и «влияние» (impact). Которые, как известно, сводятся к игре шрифтами (ну и можно ещё баззвардов подсыпать).

                                                                                                  Ну а дальше — имеем то, что имеем. Никто не будет писать хороший код, если куда важнее — создать хорошую презентацию и «документ о дизайне» (design doc). То, что в результате получится дерьмо, которое будет жрать ресурсы как не в себя и тормозить (см. GMail) — никого не волнует. За то, что будет порождено 100500 продуктов, ни одним из которых нельзя будет пользоваться (Hangouts, Allo, Duo, какой-там-ещё был высер, якобы конкурирующий с WhatsApp?) — никто «втыка» не получит.

                                                                                                  В резльтате — я реально не знаю ни одного пользовательского продукта, сделанного в Google в последние лет 5-7 и получившего популярность. Backend? Всякие TensorFlow? Да — их делают «придурки», не умеющие ублажать «эффективных манагеров» и не получающие много плюшек, но и зато не имеюшие уж очень много манагеров на шее.

                                                                                                  Frontend? От плохого к худшему, уж извините.

                                                                                                  P.S. Это, впрочем, нормально: Microsoft тоже через этот этап прошёл. Там, чтобы выправить ситуацию пришлось CEO выпереть… посмотрим что в Google потребуется…
                                                                                                    0
                                                                                                    Инжинеры в гмыле себе немного оставили mail.google.com/mail/u/0/h/1pq68r75kzvdr/?v%3Dlui
                                                                                                    Сначала пользовались ей иногда, теперь постоянно, т.к. стандартная версия даже на десктопе уже достала тормозить.
                                                                                                      0

                                                                                                      Тема от подходов к программированию плавно перешла к управлению продуктами. Tensorflow на самом деле хорош. Облачные продукты у них нормальные. Интерфейс, конечно, шлак и документация постоянно устаревшая, но богатство возможностей поражает. Андроид не плох. Конечно он родился больше чем "5-7 лет назад", но новые версии вполне вменяемые.


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

                                                                                          0
                                                                                          Он даёт очень много возможностей по сравнению, например, с аутлуком.
                                                                                          Я, вообще-то сказал достаточно однозначно: «не даёт ничего по сравнению с тем же GMail'ом десятилетней давности». Когда уже и чаты и всякие прочие плюшки (даже тот самый Google Buzz) уже были — а таких объемов… добра в кода и таких тормозов — не было и в помине.

                                                                                          И я даже знаю какие вещи (в том числе полезные) за это время появились (скажем Priority Inbox) — но я не знаю ни одной из ничего, что нельзя было реализовать в версии той же десятилетней давности, требующей на порядок меньше ресурсов и на порядок более отзывчивой…
                                                                                        0
                                                                                        Да, но если вы этот цикл запихнете в функцию reverseString, то чтение вызова оной также займет мгновение. В сплите-джойне вы точно так же кучи циклов прячете за фасадом библиотеки.
                                                                                        0
                                                                                        Я то же самое про РНР постоянно слышу. А проблема та же)
                                                                                          0
                                                                                          Как я ниже уже сказал, вопросы к языку тоже есть. Например, почему map и filter аллоцируют объекты.
                                                                                          +1
                                                                                          Как выяснилось, если применять стандартные вещи без понимания, тестирования, тяп-ляп и коротко — попадёшь на грабли. Автор начал писать за это, но тут же попал на следующие грабли, с составными символами. А, скажем, на macOS, iOS, стандартная нормализация NFD.
                                                                                    +1
                                                                                    Если под «оптимальностью» имелось ввиду «оптимальное по размеру кода и очевидности», то зачем так извращаться? Можно ведь просто использовать for…
                                                                                    function func(str) {
                                                                                    	ret = "";
                                                                                    	for(i = str.length; i >= 0; i--)
                                                                                    		ret += str.substr(i, 1);
                                                                                    	return ret;
                                                                                    }
                                                                                    
                                                                                      +2
                                                                                      Разве каждую итерацию не будет повторное выделение памяти?
                                                                                      По идее здесь нужен билдер, который будет принимать сразу размер и потом заполнять не меняя размер. но я не знаю как это в JS делается.
                                                                                        0
                                                                                        Я тоже не уверен, что с этим будет делать JS. Скорее всего этот способ займет много памяти. Но по своей простоте и очевидности, способ по-моему самый простой. Ведь что конкретно автор имеет ввиду под «оптимально» мы пока не выяснили…
                                                                                        +10
                                                                                        Можно. Но, имхо, однострочник проще и понятнее.

                                                                                        Что касается производительности, то я плохо представляю, в каком сценарии операция реверса строки на веб-странице может стать узким местом, чтобы заниматься ее оптимизацией. Если мы пишем сервис, который должен реверсить гигабайты в секунду — это другой разговор. Но для веб-страницы не так важно, выполнится реверс строки за 1мкс или за 2мкс.

                                                                                        Вот кстати бенчмарк с разными способами: jsperf.com/string-reverse-function-performance
                                                                                          +6
                                                                                          Ага, особенно учитывая что самый быстрый вариант выглядит вот так:
                                                                                          // only for-loop declaration with concatenation 
                                                                                          function reverse_06 (s) {
                                                                                            for (var i = s.length - 1, o = ''; i >= 0; o += s[i--]) { }
                                                                                            return o;
                                                                                          }
                                                                                            0
                                                                                            Да, на моей машине jsperf показывает для этого варианта 2.6 миллионов операций в секунду, а для однострочника — всего 1.6 миллионов операций в секунду.

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

                                                                                              o += s[i--]


                                                                                              Спасибо, не надо такого.

                                                                                                0
                                                                                                А почему не вот так?
                                                                                                function reverse_06 (s) {
                                                                                                  for (var i = s.length, o = ''; i--; o += s[i]) { }
                                                                                                  return o;
                                                                                                }
                                                                                                
                                                                                                  +4
                                                                                                  Почему люди (особенно с сишным бекграундом) так стараюстя уместить максимальное количество сайдэффектов на единицу площади? Если расписать функцию нормально строк в 5 она будет читаться сильно проще, чем этот остроумный вариант использующий все дополнительные свойства операций.
                                                                                                    0
                                                                                                    Этим страдают джуны, которые хотят показать таким образом своё мастерство в знании ЯП.
                                                                                                      0
                                                                                                      Этим страдают те, кому нечем заняться, и хочется слегка пошутить на тему кода.
                                                                                                      В проект это совать… Комментов больше чем кода напишешь.
                                                                                                        0
                                                                                                        Комментов больше чем кода напишешь.
                                                                                                        Там не может быть ни одного коммента. Ну никак. Весь кайф он наблюдейния глаз человека узревшего чего-нибудь типа if any(iter) and not any(iter): (это, правда Python) потеряется…
                                                                                                      +2
                                                                                                      Я как программист С++ с большим опытом могу сказать, что это типичная болезнь многих С/С++ программистов. Когда я только научился писать на С++ более-менее хорошо, я тоже так писал. Но со временем приходит понимание, что твой код ещё ВНЕЗАПНО читают другие люди, и тогда начинаешь писать уже нормально, не экономя переносы строк и символы. К сожалению, понимание приходит далеко не всем. Знаю даже опытных людей, с опытом в десятки лет, которые выдают всякие s = i++ + k * ++m; Вроде и не UB и всё работает по стандарту, а хочется плеваться.
                                                                                                        0

                                                                                                        Буквально на днях читал доклад александреску, причем на сишарпе, и там пожалуйста, то же самое… А ведь для кого-то это икона.

                                                                                                          0
                                                                                                          Глянул пример, подозреваю, что там реально код оптимизировался именно по размеру. Там слайды презентаций, поэтому и приходилось всё умещать всё в 6-8 строк.
                                                                                                      0
                                                                                                      Почему не
                                                                                                      function reverse_06 (s) {
                                                                                                        var o = '';
                                                                                                        for (var i = s.length; i >= 0; i--) {
                                                                                                           o += s[i];
                                                                                                        };
                                                                                                        return o;
                                                                                                      }
                                                                                                      

                                                                                                      Тогда уже.
                                                                                                      Хотя почти это же написали выше.
                                                                                                  +1
                                                                                                  Ну вот, вы предложили решение с квадратичной сложностью. NO HIRE!
                                                                                                    0
                                                                                                    по идее на первой итерации это должно упасть, мы сразу же выходим за границы массива.
                                                                                                    i = str.length — это индекс элемента за последним.
                                                                                                    +1
                                                                                                    Строго говоря «эффективно» и «оптимально» это две формы одного и того же понятия.
                                                                                                    Потому что эффективность так же требует критерия как и оптимальность. Реализация может быть эффективна по: тактам процессора, используемой памяти, простоте дальнейшего сопровождения, эффекту производимому на вопрошающего и т.д. и т.п. И вовсе не факт что это будет одна и та же реализация.
                                                                                                    +18
                                                                                                    У браузеров сейчас довольно продвинутые JIT-компиляторы. Я недавно офигел, когда реализовал force-directed алгоритм рисования графа двумя способами:

                                                                                                    • Максимально разжеванным для компилятора с циклами вида for (let i=arr.length-1; i>=0; --i), заранее выделяя все массивы нужной длины, с выносом всего неизменного в константы, явным приведением типов в духе asm.js и хранением всех данных в плоских типизированных массивах.
                                                                                                    • Модном сейчас функциональном стиле с кучей лямбд, map, созданием десятка промежуточных массивов, хранением данных во вложенных словарях с обращением по строковому идентификатору.

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

                                                                                                    Относительно кода автора, уже были сделаны бенчмарки, сравнивающие время выполнения обращения строк и выяснилось, что разница примерно в 2 раза по сравнению с обычными циклами: jsperf.com/string-reverse-function-performance (код автора: «in-built functions»). Да, не оптимально, но в рамках допустимого: если это не узкое место в программе, то решение в одну строчку гораздо более читабельное и поддерживаемое. Думаю, если бы не умные оптимизации компилятора, разница была бы раз в десять.
                                                                                                      +5
                                                                                                      А я вот в своё время поржал, что замена const на немодный var может ускорить некий синтетический код раза так в два.
                                                                                                        0
                                                                                                        у меня бывало наоборот — числовой const начал инлайниться по месту употребления, но это происходило нерегулярно и без гарантии. Делал это встроенный минификатор Webpack
                                                                                                        +1
                                                                                                        и оказалось, что время их выполнения абсолютно одинаково и примерно равно времени выполнения такого же кода на C.

                                                                                                        Надо думать второй вариант будет потреблять больше памяти и чаще дергать сборщик мусора, т.к. функциональный стиль подразумевает иммутабельность aka «создание десятка промежуточных массивов»
                                                                                                          +3

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

                                                                                                            +2
                                                                                                            Ну, откровенно говоря, бенчмарки такое не показывают. Сборщик мусора подл тем, что «останавливает мир» в непредсказуемые моменты времени когда-то потом. А на каждый прогон теста создаётся свой мир с последующей сборкой мусора. Надо профилировать память в реально работающем коде, что узнать как обстоят дела.
                                                                                                            0

                                                                                                            Чаще — это хорошо. Чем больше мусора вычищается из Gen0, не переходя в Gen1, тем лучше. Gen0 быстрый.

                                                                                                              0
                                                                                                              «создание десятка промежуточных массивов»

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

                                                                                                              +9
                                                                                                              я добавлю, что на том бенчмарке тестировалась строка длиной в 61 символ

                                                                                                              а тут проверяли строки разной длины, и оказалось, что при длине >64 символов метод с цепочками начинает обгонять метод с циклом.

                                                                                                              Смысл в том, что перформанс надо тестировать в конкретных условиях
                                                                                                              –45
                                                                                                              Мир фронтенда — это апофеоз неэффективности. Само собой, когда туда идут только бракованные программисты.
                                                                                                                +6
                                                                                                                Я бы охерел, если бы на вакансию С++ программиста кто-то для реверса строки сначала её в отдельный список/массив конвертировал.

                                                                                                                А C++ что ли не умеет в итераторы?

                                                                                                                  +5
                                                                                                                  Здравствуйте. Перформанс этого метода конкретно в JS неоднозначен и требует тестирования в конкретных боевых условиях. Еще в 2009 году были проведены тесты, в которых было показано, что если строка превышает 64 символа в длину — метод str.split('').reverse().join(''); внезапно начинает обгонять метод с циклом. Я не говорю — этот тест актуален и сейчас. Я говорю — надо тестировать перформанс в конкретных боевых условиях.

                                                                                                                  shamasis.net/2009/09/javascript-string-reversing-algorithm-performance

                                                                                                                  На всякий случай, если ссылка сдохнет.

                                                                                                                  // быстрее на строках > 64 символов
                                                                                                                  String.prototype.reverse = function() {
                                                                                                                      return this.split('').reverse().join('');
                                                                                                                  };
                                                                                                                  
                                                                                                                  // быстрее на строках < 64 символов
                                                                                                                  String.prototype.reverse = function() {
                                                                                                                      var i, s='';
                                                                                                                      for(i = this.length; i >= 0; i--) {
                                                                                                                          s+= this.charAt(i);
                                                                                                                      }
                                                                                                                      return s;
                                                                                                                  };
                                                                                                                  

                                                                                                                    +3

                                                                                                                    Первый вариант имеет сложность O(n), а второй вариант — O(n^2), так как на каждой итерации происходит конкатенация строк. Правильно было бы сравнивать вариант с цепочкой вызовов с этим:


                                                                                                                    String.prototype.reverse = function() {
                                                                                                                        var i, a= [];
                                                                                                                        for(i = this.length; i >= 0; i--) {
                                                                                                                            a.push(this.charAt(i));
                                                                                                                        }
                                                                                                                        return a.join('');
                                                                                                                    };

                                                                                                                    Этот вариант так же имеет сложность O(n), но потребляет меньше памяти (с точностью до коэффициента, так как потребление памяти у них одинаковое — O(n)).

                                                                                                                      +1
                                                                                                                      конкатенация строк в JS — не то же, что конкатенация строк в Java

                                                                                                                      stackoverflow.com/questions/16696632/most-efficient-way-to-concatenate-strings-in-javascript
                                                                                                                      image
                                                                                                                        0
                                                                                                                        Хм, интересно, не знал. Спасибо за информацию.
                                                                                                                          +1
                                                                                                                          Пожалуйста. Я сам постоянно страдаю от желания оптимизировать все эти цепочки, и если копаться в моем коде — наверняка можно найти кучу вещей, которые можно было бы записать короче, а не циклами. Мне до сих пор непривычно, что конкатенация строк плюсом самая быстрая в JS.

                                                                                                                          Но, как я читал, в Java идут разговоры о том, чтобы в следующих версиях улучшить реализацию String так, чтобы конкатенация по дефолту происходила так же быстро, как сейчас через StringBuilder. Так что, вполне вероятно, лет через 10 мы все забудем про конкатенацию строк как дополнительный n )

                                                                                                                          Я часто работаю со строками (пишу мини-парсеры для сменного контента в мини-играх), поэтому постоянно ищу, где бы улучшить обработку строк — но пока прихожу к выводу, что оптимизацию надо делать отдельной задачей, после того, как реализован проект — и там уже менять то, что дает заметный для пользователя эффект тормозов
                                                                                                                          +1
                                                                                                                          Круто. В 2011 было наоборот, из-за этого у нас всюду, где код для старых браузеров, join массива.
                                                                                                                            +1
                                                                                                                            Похоже что даже в разных версиях SpiderMonkey, оптимизации немного разные. Впрочем, разница невелика. А вот V8 действительно сильно оптимизирован на конкатенацию.
                                                                                                                            Лиса
                                                                                                                            image

                                                                                                                            Хром
                                                                                                                            image

                                                                                                                            Хотелось бы ещё увидеть результат с инициализацией массива через new Array(10000). Без него как-то не интересно.
                                                                                                                              0
                                                                                                                              Как и ожидалось, предварительно выделенный массив работает быстрее, чем обычный. Но оптимизированная конкатенация, там где она есть, всё равно даёт лучшие результаты.
                                                                                                                              Лиса
                                                                                                                              image

                                                                                                                              Хром
                                                                                                                              image

                                                                                                                              Ну и для полноты картины:
                                                                                                                              Edge
                                                                                                                              image

                                                                                                                              IE
                                                                                                                              image

                                                                                                                              Опера 12
                                                                                                                              image

                                                                                                                              Ссылка на модифицированный тест
                                                                                                                            +1

                                                                                                                            Ага, а реаллокация массива в таком варианте, значит, не происходит?


                                                                                                                            Тогда уж лучше так?


                                                                                                                            String.prototype.reverse = function() {
                                                                                                                                var i, a= this.slice(0);
                                                                                                                                for(i = this.length; i >= 0; i--) {
                                                                                                                                    a[this.length - i] = this[i];
                                                                                                                                }
                                                                                                                                return a;
                                                                                                                            };
                                                                                                                              +1

                                                                                                                              Да, точно, совсем забыл. Можно проинициализировать еще так:


                                                                                                                              new Array(this.length)
                                                                                                                          +3
                                                                                                                          А вы видите требования к эффективности или производительности кода? Их нет.

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

                                                                                                                            Просто так сплитнуть с другой половиной не выйдет, потому что utf8 же и символ может занимать разное количество байт. Да и те же умлауты, у вас немецкий текст может в кашу превратиться.

                                                                                                                              0
                                                                                                                              Если это UTF строка, то по логике, взятие символа b=a[i] или замена a[i]=c, должно обрабатываться корректно, в не зависимости из скольких байт состоит, т.е. с учетом стандарта UTF и этих его эмодзи, не к ночи будут упомянуты.
                                                                                                                                0
                                                                                                                                Это UTF-16 строка. Там суррогатные пары попадаются.
                                                                                                                                  0

                                                                                                                                  Только взятие символа в таком случае имеет сложность oN, а обход всей строки посимвольно квадратичную.

                                                                                                                                    0
                                                                                                                                    Простите, почему? Если я читаю всю строку конечным автоматом, то я получаю все символы не совершая для этого никаких лишних действий. И сложность обхода остаётся линейной.
                                                                                                                                      0

                                                                                                                                      Есть проблема в том, чтобы юникод читать конечным автоматом с конца строки, а вам символы с конца строки тоже нужно читать целиком, а если прочитать её по порядку в массив то по факту решение такое же как в жс было изначально.

                                                                                                                                        +1
                                                                                                                                        Есть проблема в том, чтобы юникод читать конечным автоматом с конца строки

                                                                                                                                        Не вижу в этом проблемы. Вторая часть суррогатных пар находится в собственном диапазоне. Прочитав её, я знаю, что это не символ, и перед ней стоит первая часть суррогатной пары.
                                                                                                                                          0

                                                                                                                                          Хм, ну тут я показал свое незнание. Но есть ещё вопрос, сколько по времени займёт поменять местами символ и суррогатную пару?

                                                                                                                                            0
                                                                                                                                            Ну, мы же не в исходной строке меняем, а формируем новую строку.
                                                                                                                                            Вот, мне было нечем заняться, и я написал генератор, перечисляющий кодовые точки в обратном порядке
                                                                                                                                            function* pointsFromEnd(str){
                                                                                                                                              let i = str.length, s="";
                                                                                                                                              for(;i--;){
                                                                                                                                                let a = str[i];
                                                                                                                                                if(s){
                                                                                                                                                  yield a+s;
                                                                                                                                                  s="";
                                                                                                                                                }
                                                                                                                                                else if(a>="\uDC00" && a<="\uDFFF"){
                                                                                                                                                  s=a;
                                                                                                                                                }
                                                                                                                                                else{
                                                                                                                                                  yield a;
                                                                                                                                                }
                                                                                                                                              }
                                                                                                                                            }
                                                                                                                                            
                                                                                                                                              0

                                                                                                                                              А в чем разница тогда? Экономия трети памяти, но более медленный и костыльный код в котором для длинных строк могут быть миллионы вызовов этой функции.
                                                                                                                                              А чтобы сделать обработку эмодзи из поста код придётся вообще целиком выкинуть.

                                                                                                                                                0
                                                                                                                                                А в чем разница тогда?

                                                                                                                                                По сравнению с чем?
                                                                                                                                +1

                                                                                                                                Не просто норма, но и рекомендуемый подход. Основной довод — читабельность и простота поддержки кода. С точки зрения скорости вы правы, не самый быстрый способ.

                                                                                                                                  0
                                                                                                                                  Да, и мы удивляемся, почему сайты стали такие медленые :)
                                                                                                                                    0
                                                                                                                                    split и join — это эффективно?

                                                                                                                                    Зависит от реализации.

                                                                                                                                    Но что мешает без сплита сразу писать в массив и его конвертировать в строку? Разве это не будет эффективнее?

                                                                                                                                    если reverse() дает итератор, а не массив, то будет так же эффективно. Другое дело, что в ЖС нет концепции итераторов, и каждый filter/map/..., которые можно было бы выполнять по цепочке каждый раз аллоцируют объекты.

                                                                                                                                    А вообще в ЖС есть намного более печальные способы убить производительность, чем сделать одно лишнее копирование. Держать представление всех объектов в 3 разных местах, например.
                                                                                                                                      0
                                                                                                                                        0
                                                                                                                                        Их все еще нет, пока 99% проектов транспилятся в ES5.
                                                                                                                                          0

                                                                                                                                          И что? Внутри транспилированного кода это же будет не конечным массивом после каждой операции представлено, а неким объектом-итератором.

                                                                                                                                            0
                                                                                                                                            Объект-итератор скорее всего будет дороже, чем просто скопировать массив.

                                                                                                                                            Смысл итераторов в том, что это по идее zero cost, который развернется оптимальным образом.
                                                                                                                                              0

                                                                                                                                              Итераторы в JS — это тоже объекты: https://www.ecma-international.org/ecma-262/6.0/#sec-createstringiterator

                                                                                                                                                0
                                                                                                                                                и? Это никак не опровергает того факта, что работа с итератором может быть чаще дороже чем с массивом.

                                                                                                                                                Смысл итератора в том, чтобы это была абстракция времени компиляции, которая полностью убирается в рантайме.
                                                                                                                                                  0

                                                                                                                                                  Может быть дороже, может быть дешевле. Нужно проверять экспериментально.

                                                                                                                                            0
                                                                                                                                            Только те, кому нужна поддержка IE или Opera Mini (одному проценту проектов). Все остальные браузеры уже давно поддеживают.
                                                                                                                                              0
                                                                                                                                              Ну давайте проведем опрос. Я уверен, что ES5 таргет основной с большим отрывом.
                                                                                                                                                +1
                                                                                                                                                Я тоже думаю ES5 основной target. А ещё можно модно написать for… of из ES6 для итерации по массиву и последний Хром будет работать почти так же быстро, как и просто проход по массиву. А вот в Firefox заметно медленнее. Поэтому транспиляция в ES5 даст не только совместимость, но ещё и лучше скорость в некоторых случаях.
                                                                                                                                                  0
                                                                                                                                                  А я уверен, что es2017, ибо отлаживать пониженные async-await — то ещё развлечение.
                                                                                                                                                    0

                                                                                                                                                    Статистику в студию.