>> (>=20, но по вероятности сильно < n) — скорее всего ничтожна, по сравнению с миллионами основного массива. Остаётся правда краевой момент с полностью отсортированным исходным массивом.
Так храните свои 20 чисел в дереве (или любой другой структуре данных, поддерживающей): - упорядоченность - поиск за O(log(n)) - вставку O(log(n)) - удаление минимального O(log(n))
Я со своей point-of-view (сервера для высоконагруженных решений) скорее согласен с вами. Но не является ли наша точка зрения следствием искажения наших предметных областей.
Вот возьму какой-нибудь свой код на пайтоне (условный xmlrpc-server, обрабатывающий вспомогательные запросы) - там же вообще нет списков в явном виде (очереди \ пулы трэдов в наличии - т.е. это не тот код, который можно писать "совсем не приходя в сознание").
Т.е. вопрос а насколько условному "бизнес-программисту" (получающему свою вполне приличную ЗП в условном Сбер-Техе, и между прочим решающему реальные задачи) нужно знание списков - весьма актуален.
Зависит ещё от коллекции. В массиве в один поток на регистрах общего назначения - упрётся в АЛУ В массиве в один поток с SIMD - упрётся в шину В списке в один поток - упрётся в дата-столы (ожидание кэша) и тут как раз мультитрэдинг подходящая оптимизация.
Коллега вопрос вам: А зачем, как вам кажется нужен большой ход клавиш? Мне вот субьективно удобнее - но почему не пойму (плюс видел где-то статистику, которая говорит, что с большим ходом скорость набора таки падает).
Клава действительно очень неплохая (в итоге правда взял себе очень похожую Thermaltake с silver-свичами).
НО хочется отметить, что большинство знакомых разработчиков, это я на работу новую клаву приносил и спрашивал - всё равно предпочли бы какую-то хорошую мембранку.
Игры (вернее игровые движки, конечно на сегодня) научили использовать многие ядра через конвейризацию (Там ещё CacheFrendly данные чезер "Structure of Arrays вместо Array of Structures" завезли).
Когда каждая стадия конвейра - отдельный thread, выполняющий одну конкретную задачу над всеми объектами (унификация через SoA помогает). Ну а ОС уже планирует все твои потоки на процессорные ядра.
На выходе после всех курсов мои навыки: java, spring (core, boot, cloud, jpa, jdbc, security, mvc, data), hibernate, mongo db, elasticksearch, apache kafka, oracle, postgres, maven, tomcat, servlet api, jsp, junit, testng, selenium webdriver, postman, jmeter, html, css, bootsrtrap, javascript, typescript, jquery+plugins, react, redux, git и вполне возможно, что я что-то забыл.
Вот я, если честно, в небольшом недоумении. Я вот не java-программист, но вроде бы навыки относительно "взрослые". Как вообще такое можно выучить за 1.5 года с нуля? Скорее всего курсы создают, причём намеренно создают, чтобы им несли деньги охотнее, в голове человека превратную картину относительно того, что такое "навык в технологии".
В итоге если бы мне в резюме написали такой список навыков с 0, за 1.5 года, после курсов - я бы считал, что звать такого человека на собеседование просто трата времени.
>> Так я ведь не про то. Сейчас складские работники плюют в потолок целый день и докидывают по пачке чипсов там, где не хватает одной. А достаточно следить, чтобы не оставалось 0.
Расскажите это складским работникам Амазона (которые ходят в памперсах, чтобы сэкономить время перекуров), или работникам условной «Шестёрочки», в которой тоже люди особо не сидят без дела.
Везде бизнес (набрав достаточно компетенции, БигДата в помощь) сокращает издержки по-максимуму.
Мой поинт в том, что в оптимизирующем компиляторе C / C++ вопрос не в том «вводить UB или не вводить», а в том «насколько агрессивно полагаться на отсутствие UB в компилируемом коде».
В том числе из-за алгоритмической неразрешимости (на практике мы просто куда раньше упрёмся во время компиляции) доказательства отсутствия UB.
>> Что вот совсем никогда не разрешим?
«алгоритмически неразрешим» без дополнительных указаний означает, что МОЖНО написать такую программу, которую совершенно никак невозможно корректно проанализировать (обычно доказывают или через сведение к проблеме останова или к через имитацию тьюринг-полного языка).
>> и часто в программах…
Вот смотрите, с т.з. компилятора: если в функцию пришло два внешних указателя — то без шансов что-то про них доказать (в том числе часть случаев — доказать можно было бы возможно, но для этого надо заново запустить межпроцедурный анализ, а уже нельзя, т.к. он делается на другом представлении). Остаётся:
— ничего не оптимизировать;
— дублировать код для случаев «непересекающихся» и «пересекающихся» объектов; — работать, как будто нет UB;
— взять «rust», с более ограниченным набором возможностей в rust-safe, чем C.
Поэтому опция «сделаем вид что UB в коде нет» — единственная возможная (на принципиальном уровне) для компиляторо-писателей С/С++.
Агрессивность — можно было бы и снизить.
Анализ алиасов указателей в C-коде алгоритмически неразрешим. Собственно этого одного достаточно, чтобы сломать почти любую оптимизацию.
Поэтому у вас ровно два варианта:
— не проводить оптимизации
— рассчитывать на то, программист не получает доступ к вашей переменной через «достаточно хитрый alias».
У меня от Хаскеля впечатление такое, что там 80% кода писать ± просто.
А вот оставшиеся 20% (это как правило «большой стейт реального мира вокруг») настолько сложно, что почти любая программа кроме «олимпиадной задачки на AVL-tree» будет сложнее чем её императивный аналог.
Для конкретики: предположим мне, относительному новичку в Хаскель, сегодня в 2021 году надо писать что-то с GUI.
Что для этого есть под Хаскель (хоть немного дружественного)?
«всё» на стек — это в смысле хранение нераспределённых виртуальных регистров (тех, которым места не хватило) на стеке или это в смысле все регистры кроме непосредственно нужных для очередной инструкции на стеке?
Это две больших разницы и во второй вариант, без доп-подробностей\оптимизаций слабо верится.
>> Время от времени мне попадаются новости о том, что кто-то в одиночку (и за приемлемое время) написал рабочий компилятор C.
Крайне расплывчатая фраза.
а) Я написал интерпретатор C (с веб-мордой для студентов) — я написал компилятор?
б) Я написал компилятор C в байт-код (потому, что не хочу заморачиваться с форматом ELF) и к нему интерпретатор — я написал компилятор C?
в) Я написал компилятор, но он создаёт только stand-alone бинарник (и не умеет использовать *.so-библиотеки ) — я написал комилятор С?
г) Я написал компилятор, но не работающий в 0м кольце защиты, я написал компилятор?
… пошли дальше…
Я написал «парсер-лексер-синтаксер — генератор IR» и отдал всё это LLVM — я написал компилятор?
…
========================
Что вообще значит «написать компилятор языка C», если из 4 обязательных этапов (7 с оптимизациями разных типов) можно 0 написать самостоятельно, а можно все 7?
1. Частота памяти — это на самом деле просто bandwidth (частота конденсаторной памяти почти не меняется).
2. Игры, заметно сильнее, чем приложения перешли на Cache-Frendly (которое скорее Memory Access Frendly) паттерн разработки.
Грубо говоря «стандартное приложение» — это Array of Structures (Objects), а игра — это Structure of Arrays, где обработка каждого следующего «тика игры» конвейризирована.
Исходя из этого:
а) Скорее игры способны хорошо утилизовать бОльший bandwidth DDR5.
б) Приложения гораздо менее Cache Frendly — соответственно и выигрыша от повышения «частоты — а на самом деле ширины канала» получат меньше.
Мне кажется, что формат научно-популярных книг очень хорошо подходит для «прокачки английского».
Во-первых «научпоп» — в принципе должен хорошо зайти читателям хабра
Во-вторых он обычно не такой сложный и написан образованными людьми (во всяком случае не такой сложный, как Худ.Лит, где писатель пишет «эстетичный» текст, используя не самые востребованные слова)
В-третьих — науч-поп предрасположен к тому, чтобы вводить новую лексику постепенно. Пока тема главы раскроется — это 5-10 страниц. А новых понятий для этой главы конечное количество.
Это троллинг такой? Данные из памяти в кэш процессора загружаются страницами, время доступа к любой странице памяти — одинаковое.
1. Данные в кэш загружаются кэш-банками
2. На NUMA время доступа к разным участкам памяти разное (в частности можно управлять выделением памяти в «родной для процессора» памяти).
В теории — наверняка да (натипомонопольное законодательство один из… хм столпов гос-вмешательства).
А на практике наверняка есть нюансы, иначе я не понимаю как тогда PayPal (в недавнем времени) и Master \ Visa \ AE (давно и закрепить поныне) смогли добиться «недескриминирующих их клиентов условий»?
>> (>=20, но по вероятности сильно < n) — скорее всего ничтожна, по сравнению с миллионами основного массива. Остаётся правда краевой момент с полностью отсортированным исходным массивом.
Так храните свои 20 чисел в дереве (или любой другой структуре данных, поддерживающей):
- упорядоченность
- поиск за O(log(n))
- вставку O(log(n))
- удаление минимального O(log(n))
>> В 99% случае всё, что надо знать о сортировке
Устойчивость \ неустойчивость зачастую важна. Но это, конечно, в мануале правильнее читать, чем помнить.
Я со своей point-of-view (сервера для высоконагруженных решений) скорее согласен с вами. Но не является ли наша точка зрения следствием искажения наших предметных областей.
Вот возьму какой-нибудь свой код на пайтоне (условный xmlrpc-server, обрабатывающий вспомогательные запросы) - там же вообще нет списков в явном виде (очереди \ пулы трэдов в наличии - т.е. это не тот код, который можно писать "совсем не приходя в сознание").
Т.е. вопрос а насколько условному "бизнес-программисту" (получающему свою вполне приличную ЗП в условном Сбер-Техе, и между прочим решающему реальные задачи) нужно знание списков - весьма актуален.
Зависит ещё от коллекции.
В массиве в один поток на регистрах общего назначения - упрётся в АЛУ
В массиве в один поток с SIMD - упрётся в шину
В списке в один поток - упрётся в дата-столы (ожидание кэша) и тут как раз мультитрэдинг подходящая оптимизация.
Коллега вопрос вам:
А зачем, как вам кажется нужен большой ход клавиш? Мне вот субьективно удобнее - но почему не пойму (плюс видел где-то статистику, которая говорит, что с большим ходом скорость набора таки падает).
Клава действительно очень неплохая (в итоге правда взял себе очень похожую Thermaltake с silver-свичами).
НО хочется отметить, что большинство знакомых разработчиков, это я на работу новую клаву приносил и спрашивал - всё равно предпочли бы какую-то хорошую мембранку.
Ну и стучит.
Bu
Игры (вернее игровые движки, конечно на сегодня) научили использовать многие ядра через конвейризацию (Там ещё CacheFrendly данные чезер "Structure of Arrays вместо Array of Structures" завезли).
Когда каждая стадия конвейра - отдельный thread, выполняющий одну конкретную задачу над всеми объектами (унификация через SoA помогает).
Ну а ОС уже планирует все твои потоки на процессорные ядра.
На выходе после всех курсов мои навыки: java, spring (core, boot, cloud, jpa, jdbc, security, mvc, data), hibernate, mongo db, elasticksearch, apache kafka, oracle, postgres, maven, tomcat, servlet api, jsp, junit, testng, selenium webdriver, postman, jmeter, html, css, bootsrtrap, javascript, typescript, jquery+plugins, react, redux, git и вполне возможно, что я что-то забыл.
Вот я, если честно, в небольшом недоумении. Я вот не java-программист, но вроде бы навыки относительно "взрослые". Как вообще такое можно выучить за 1.5 года с нуля?
Скорее всего курсы создают, причём намеренно создают, чтобы им несли деньги охотнее, в голове человека превратную картину относительно того, что такое "навык в технологии".
В итоге если бы мне в резюме написали такой список навыков с 0, за 1.5 года, после курсов - я бы считал, что звать такого человека на собеседование просто трата времени.
Расскажите это складским работникам Амазона (которые ходят в памперсах, чтобы сэкономить время перекуров), или работникам условной «Шестёрочки», в которой тоже люди особо не сидят без дела.
Везде бизнес (набрав достаточно компетенции, БигДата в помощь) сокращает издержки по-максимуму.
В том числе из-за алгоритмической неразрешимости (на практике мы просто куда раньше упрёмся во время компиляции) доказательства отсутствия UB.
>> Что вот совсем никогда не разрешим?
«алгоритмически неразрешим» без дополнительных указаний означает, что МОЖНО написать такую программу, которую совершенно никак невозможно корректно проанализировать (обычно доказывают или через сведение к проблеме останова или к через имитацию тьюринг-полного языка).
>> и часто в программах…
Вот смотрите, с т.з. компилятора: если в функцию пришло два внешних указателя — то без шансов что-то про них доказать (в том числе часть случаев — доказать можно было бы возможно, но для этого надо заново запустить межпроцедурный анализ, а уже нельзя, т.к. он делается на другом представлении). Остаётся:
— ничего не оптимизировать;
— дублировать код для случаев «непересекающихся» и «пересекающихся» объектов;
— работать, как будто нет UB;
— взять «rust», с более ограниченным набором возможностей в rust-safe, чем C.
Поэтому опция «сделаем вид что UB в коде нет» — единственная возможная (на принципиальном уровне) для компиляторо-писателей С/С++.
Агрессивность — можно было бы и снизить.
Анализ алиасов указателей в C-коде алгоритмически неразрешим. Собственно этого одного достаточно, чтобы сломать почти любую оптимизацию.
Поэтому у вас ровно два варианта:
— не проводить оптимизации
— рассчитывать на то, программист не получает доступ к вашей переменной через «достаточно хитрый alias».
На практике выбран второй вариант.
А вот оставшиеся 20% (это как правило «большой стейт реального мира вокруг») настолько сложно, что почти любая программа кроме «олимпиадной задачки на AVL-tree» будет сложнее чем её императивный аналог.
Для конкретики: предположим мне, относительному новичку в Хаскель, сегодня в 2021 году надо писать что-то с GUI.
Что для этого есть под Хаскель (хоть немного дружественного)?
Это две больших разницы и во второй вариант, без доп-подробностей\оптимизаций слабо верится.
А в RUST уже завезли формальную memory model для языка?
То есть этот тот момент, когда с т.з. софистики вопрос на 10/10, но с точки зрения практики — «проклятая реальность» пока ещё слишком сильна.
Крайне расплывчатая фраза.
а) Я написал интерпретатор C (с веб-мордой для студентов) — я написал компилятор?
б) Я написал компилятор C в байт-код (потому, что не хочу заморачиваться с форматом ELF) и к нему интерпретатор — я написал компилятор C?
в) Я написал компилятор, но он создаёт только stand-alone бинарник (и не умеет использовать *.so-библиотеки ) — я написал комилятор С?
г) Я написал компилятор, но не работающий в 0м кольце защиты, я написал компилятор?
… пошли дальше…
Я написал «парсер-лексер-синтаксер — генератор IR» и отдал всё это LLVM — я написал компилятор?
…
========================
Что вообще значит «написать компилятор языка C», если из 4 обязательных этапов (7 с оптимизациями разных типов) можно 0 написать самостоятельно, а можно все 7?
1) Парсер -> лексер -> синтаксер =>
*2) глобальный анализ/оптимизация
3) генерация IR =>
*4) платформо-независимые оптимизации =>
*5) платформо-зависимые оптимизации =>
6) планирование с распределением регистров =>
7) кодогенерация.
1. Частота памяти — это на самом деле просто bandwidth (частота конденсаторной памяти почти не меняется).
2. Игры, заметно сильнее, чем приложения перешли на Cache-Frendly (которое скорее Memory Access Frendly) паттерн разработки.
Грубо говоря «стандартное приложение» — это Array of Structures (Objects), а игра — это Structure of Arrays, где обработка каждого следующего «тика игры» конвейризирована.
Исходя из этого:
а) Скорее игры способны хорошо утилизовать бОльший bandwidth DDR5.
б) Приложения гораздо менее Cache Frendly — соответственно и выигрыша от повышения «частоты — а на самом деле ширины канала» получат меньше.
Во-первых «научпоп» — в принципе должен хорошо зайти читателям хабра
Во-вторых он обычно не такой сложный и написан образованными людьми (во всяком случае не такой сложный, как Худ.Лит, где писатель пишет «эстетичный» текст, используя не самые востребованные слова)
В-третьих — науч-поп предрасположен к тому, чтобы вводить новую лексику постепенно. Пока тема главы раскроется — это 5-10 страниц. А новых понятий для этой главы конечное количество.
1. Данные в кэш загружаются кэш-банками
2. На NUMA время доступа к разным участкам памяти разное (в частности можно управлять выделением памяти в «родной для процессора» памяти).
1. Данные из памяти в кэш загружаются кэш-банками
2. На NUMA скорость доступа к «своей» и «не своей» памяти отличается, может отличаться сильно
Извините, «придираюсь» именно к вам (у других много недостаточно точных утверждений — но у вас прям фактические ошибки).
В теории — наверняка да (натипомонопольное законодательство один из… хм столпов гос-вмешательства).
А на практике наверняка есть нюансы, иначе я не понимаю как тогда PayPal (в недавнем времени) и Master \ Visa \ AE (давно и закрепить поныне) смогли добиться «недескриминирующих их клиентов условий»?