Это классическая проблема, которая получила некоторый резонанс в 1986 году, когда Дональд Кнут реализовал быстрое решение с попытками хеширования в программе на 8 -страниц -, чтобы проиллюстрировать свою грамотную технику программирования. в то время как Дуг Макилрой, крестный отец каналов Unix, ответил одним -вкладышем, который был не таким быстрым, но выполнил свою работу :
.
tr -cs A-Za-z '\n' | tr A-Z a-z | sort | uniq -c | sort -rn | sed 10q
Конечно, решение Макилроя имеет временную сложность O (N log N ), где N — общее количество слов. Есть гораздо более быстрые решения. Например:
Здесь — реализация C++ с верхней границей временной сложности O ((N + k )log k ), обычно — почти линейной.
Ниже приведена быстрая реализация Python с использованием хеш-словарей и кучи со временной сложностью O (N + k log Q ), где Q — количество уникальных слов:
import collections, re, sys
filename = sys.argv[1]
k = int(sys.argv[2]) if len(sys.argv)>2 else 10
text = open(filename).read()
counts = collections.Counter(re.findall('[a-z]+', text.lower()))
for i, w in counts.most_common(k):
print(i, w)
Здесь — это чрезвычайно быстрое решение на Rust от Anders Kaseorg.
Сравнение времени процессора (в секундах):
bible32 bible256
Rust (prefix tree) 0.632 5.284
C++ (prefix tree + heap) 4.838 38.587
Python (Counter) 9.851 100.487
Sheharyar (AWK + sort) 30.071 251.301
McIlroy (tr + sort + uniq) 60.251 690.906
Примечания:
Ответ на этот вопрос весьма неоднозначен. Но основная причина заключается в том, что хотя (x86 / x86 _64 )ПК могут показаться очень разнообразными, на самом деле это не так. SBC (, часто основанные на ARM ), гораздо более разнообразны, и даже процессоры ARM могут сильно отличаться друг от друга.
Причина отсутствия разнообразия в ПК, возможно, немного основана на мнении, но я рискну предположить, что это как-то связано с Microsoft DOS, а затем с Microsoft Windows. К ним исторически предъявлялись строгие требования. Я полагаю, что в первые дни это было возможно, потому что «IBM-совместимые ПК » были широко распространены. Microsoft написала свое программное обеспечение только для этого и ни для чего другого. Позже Microsoft была настолько доминирующей, что могла просто требовать то, что им нравилось, и поставщики оборудования должны были следовать за ними.
Точно так же Intel имела такое превосходство, что, чтобы конкурировать, другие производители (, например AMD ), должны были убедиться, что их процессоры совместимы с процессорами Intel. Хотя забавным моментом в истории является то, что то, что мы сейчас называем x86 _64, на самом деле было изобретением AMD, также известным как AMD64 .
Большинство SBC основаны на ARM, и у них другая история. На самом деле ARM вообще не производит процессоры, они просто лицензируют дизайн производителям. Это позволило многим производителям настраивать эти конструкции, и коммерческого давления для их стандартизации не было.
У ПК очень стабильный набор основных инструкций. Да, разные процессоры Intel/AMD имеют некоторые дополнительные наборы инструкций для определенных расширенных функций, но в основном для запуска ОС они не так важны. Они могут повлиять на то, какие приложения вы можете запускать.
Но с ARM SBC были гораздо более существенные различия в наборах инструкций.Например, когда был создан первый Raspberry PI, они использовали ЦП ARM со встроенным аппаратным -float . В то время другие основные дистрибутивы Linux, такие как Debian, не были скомпилированы для поддержки этого. Технически они будут работать, но без них они будут гораздо медленнее.
Теперь важно понять, что основные функции ЦП и наборы инструкций используются не только ядром, но и каждым устанавливаемым программным пакетом. Если вам нужна аппаратная -поддержка float, а дистрибутив ОС не был скомпилирован для этого, вы должны повторно -скомпилировать каждый отдельный пакет в системе.
Некоторые сложные проблемы возникают из-за других особенностей процессора. Это означает, что многим SBC ARM требуется модификация ядра Linux. Теперь кажется немного выше -вершины -поставлять совершенно новый дистрибутив ради ядра. Но одно верно:
why wouldn't Raspbian work out of the box on an OrangePi
Если вам удалось решить проблемы с запуском (ниже ), вы все равно можете обнаружить, что в нем отсутствуют важные наложения ядра . В результате могут просто отсутствовать функции, или это может быть ядро, которое просто не загружается.
Запуск обычно не является причиной для выпуска полностью новой ОС. Но с ним нужно обращаться осторожно.
На ПК большая часть аппаратной инициализации либо стандартизирована, либо обрабатывается BIOS. В BIOS хранится программное обеспечение, поставляемое производителем, и оно запускается перед ОС. Затем он отвечает за поиск и запуск загрузчика.
В ARM SBC нет BIOS. Эквивалентное программное обеспечение поставляется вместе с ОС. Теперь технически ничто не мешает операционным системам с открытым исходным кодом обмениваться этой прошивкой друг с другом (см. лицензию на bootcode.bin Raspberry Ri). Но это означает, что каждая ОС должна иметь копию этой прошивки для каждого отдельного SBC... а существует много разных SBC.
Я полагаю, что другие SBC обходят это, просто отправляя свой собственный ISO существующей операционной системы. Бигльборд делает это .
Это отличный вопрос, на который, к сожалению, мало кто знает ответ, но знание которого, тем не менее, очень важно. Однако нет возможного краткого ответа, поэтому, пожалуйста, потерпите меня.
Редактировать:Эта статья подводит итог:«ARM, наконец, определила платформу, нацелившись на серверную комнату» -Ars Technica
Чтобы загрузить операционную систему, каждый компьютер запускается с этими обязательными шагами (обратите внимание на аббревиатуры):
Обратите внимание, что BDrivers в основном предназначены для инициализации некоторых компонентов материнской платы и шин.
Это означает очень разное аппаратное обеспечение x64, но одинаковую FSB и почему один iso может их всех . Вот почему вы по-прежнему можете обновить свой ПК/ноутбук с Windows XP 2005 до последней версии Windows 10 или Linux от 2021 (и выше ), когда OEM-производители уже прекратили поддержку программного обеспечения примерно в 2009 году.
Из-за чрезвычайно разнообразного аппаратного обеспечения , но также разнообразной FSB, ни один ISO-образ не может подойти для всех . Это объясняет, почему вы увидите странную бессмысленную последовательность FSB, как на Raspberry 3, где GPU запускает CPU (! ).
Изменить :Обратите внимание, что я НЕ говорю обо всем (ядре, всех системных библиотеках, программном обеспечении для конечного пользователя ), которые должны быть перекомпилированы для работы образа на платформе ARM.
Такие различия на платформах ARM означают, что получение BDrivers зависит только от доброй воли OEM-производителей , поэтому вы можете их загрузить.
К сожалению, мы уже десять лет наблюдаем, как обстоят дела с основными устройствами ARM (, например, с устройствами Android/Apple):Только OEM-производители могут обновить версию вашей ОС, поскольку только у них есть BDrivers .
Без этих BDrivers никто не сможет легко создать собственное ПЗУ или образ. Вот почему создание пользовательских ПЗУ на устройствах Android занимает так много времени и их так сложно сделать из-за обязательного обратного -инжиниринга, и что практически никто не знает, как создать собственный образ iOS или Android для устройств Apple.
Очень легко предположить, что все, что вам нужно, это иметь какую-то стандартизированную FSB на платформах ARM, чтобы все работало как на x64:
Даже по прошествии 8 лет практически невозможно иметь пользовательский/разработанный сообществом образ Windows 10 для этих устройств Surface по тем же причинам, что и для любых устройств ARM.:Это связано с тем, что Microsoft не хочет выпускать вышеупомянутые BDrivers . ].
На сегодняшний день (2021 ), все остальные продукты Microsoft Surface были выпущены на платформах x64 в течение почти десятилетия, это 22 устройства x64 на 4 устройства ARM, это очень о многом говорит...
Исключением из недавнего выпуска является Surface Pro X (октябрь 2019 г. ), который по-прежнему не может загрузить стандартный arm64
iso даже спустя 1,5 года, несмотря на наличие UEFI:Linux на Surface Pro X. Проблемы -Гитхаб
Это означает, что наличие UEFI абсолютно не гарантирует загрузки стандартного образа на платформах ARM.
Как и в UEFI на ARM, такая же ситуация и с U -Boot:No BDrivers, no image . Пусть даже надеется на унифицированную ФСБ.
Практически на всех Android-устройствах ситуация еще хуже, поскольку то, что обычно называют «загрузчиком» (или FSB ), заблокировано OEM-производителем. Устройства iOS даже не дадут вам шанса разблокировать его официальными средствами, не говоря уже о неофициальных.
Но, к сожалению, мы не видели много новостей о таких платформах SBSA с момента их создания, за исключением нескольких серверов, что указывает на то, что SBSA не может предотвратить фрагментацию.
Хуже того, очень маловероятно, что -какое-либо решение, подобное SBSA, для основных платформ (телефонов, планшетов, ПК и т. д. ), так как запланированное устаревание слишком прибыльно, и это длилось слишком долго, поэтому любые надежды на OEM-производителей, готовых вернуть это обратно, практически равны нулю, особенно на устройствах Android / iOS.
Project Treble
и Project Mainline
, поскольку они не могут заставить OEM-производителей иметь стандартизированную последовательность FSB. Цель состоит в том, чтобы предоставлять обновления системы Android независимо от ПЗУ OEM-производителей, которые застряли на определенной версии из-за запланированного устаревания. Однако это даже немного не изменило ситуацию, а разработчикам пользовательских ПЗУ стало еще сложнее. Фактически, Google, безусловно, может заставить OEM-производителей использовать стандартизированную последовательность FSB, когда они проходят программу сертифицированных устройств Android.
Но помните, что исходный код AOSP является открытым, и OEM-производители могут пойти своим путем, если Google принудит к чему-либо. Это то, что уже произошло с Huawei, телефонами Honor и другими с «HarmonyOS»:«Исход Android :больше производителей телефонов могут обратиться к HarmonyOS от Huawei» -Techradar .
В целом, обе попытки даже не добились значительного прогресса в преодолении фрагментации платформ ARM
Одна важная вещь, которая приводит к еще большей фрагментации, — это плохая привычка ARM использовать стиль разработки «скользящих -выпусков» для своих «архитектур» :
.Это часто приводит к жестокому и скрытому удалению функций без обходных путей:
В то время как x64 поддерживает совместимость с самыми первыми 64-разрядными процессорами (AMD Athlon 64 )и новейшими процессорами, ARM может не поддерживать совместимость с 32-разрядными:
armel
и armhf
даже на 32-битном ARM. Несколько вещей, о которых следует помнить и учитывать:
Такая обратная совместимость действительно предотвращает фрагментацию.
PS:Мой пост действительно тяжёлый. Если кто-то может сделать это лучше понять, я открыт для предложений.