Программирование[8]

Если у тебя слева от икса ещё 400 иксов например, что будет быстрее - проитерить по всем 4м сотням или бинарным поиском пропргыгать до первого числа, справа от которого все иксы?

Ровно тот же самый логN против линейной

бле, я думал там массив длиной тыща, а там числа от нуля до тыщи 

тогда офк лучше бинарник, рано или поздно он выиграет

А на массиве длиной в тыщу линейная сложность вдруг станет пизже логарифмической?

на рандомно заполненном массиве в тыщу у тебя есть нехилая такая вероятность, что твоих искомых чисел штуки 4

и линейная станет пизже логарифмической, тк та начнет просматривать всю левую половину массива, а достаточно было шагнуть влево 1-2 раза

 

зачем влево вправо бинарным

 

 

ты автоматически попадаешь им в худший случай, просто циклом влево вправо, пока не встретишь другое число

 

Это да, щас тоже об этом подумал. Но и цикл тоже не прям оптимально. В таком случае логичнее проверять элементы не подряд, не  n+1, n+2, n+3, n+4.. а что-то вроде бинарного поиска наоборот: n+1, n+2, n+4, n+8 итд

 

Но а на литкоде еще умнее сделали. Что-то вроде модифицированного бинарного поиска, который ищет не просто вхождение элемента, а сразу самое левое или самое правое вхождение 

 

ссылку можно?

на рандомно заполненном массиве в тыщу у тебя есть нехилая такая вероятность, что твоих искомых чисел штуки 4

и линейная станет пизже логарифмической, тк та начнет просматривать всю левую половину массива, а достаточно было шагнуть влево 1-2 раза

мне нужно и на 1к и на 10к и на 100к

числа остаются от 0 до 1000

https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

интересно чем обусловлено то что украина на 1 месте

возможно в украине очень много вкатывающихся в айти и студентов которые доходят до открытия vim

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

возможно индия и китай имеют свои аналоги stackoverflow и потому не лидируют

возможно где-то этим вещам учат в школе или универе

вообще эта стата наталкивает на мысль что в украине массовое вкатываение в айти зашло дальше чем в росссии

https://stackoverflow.blog/2017/05/23/stack-overflow-helping-one-million-developers-exit-vim/

там еще стата есть что чаще веб девелоперы не могут с vim выйти, мб у нас тренд вкатывания именно в веб сильнее чем в другие направления

в чем профит от вима, научите плс?

jquery с вимом, ебать))

Не знаю как вы а я до сих пор хз как там из него выйти

в чем профит от вима, научите плс?

jquery с вимом, ебать))

Очень быстрая навигация по тексту абсолютно без мышки (за счет кучи всяких хоткеев), онли консольный интерфейс, имеется очень много плагинов на все случаи жизни (интеграции с дебаггерами, системами сборки/контроля версий, автодополнения-подсказки, визуальная кастомизация и так далее), очень широкая распространенность. И да, сам редактор текста не тормозит в отличие от всяких модных IDEшек (но всякие тяжелые плагины вроде YouCompleteMe тормозить вполне могут).

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

Но использовать вим вместо IDE на своей локальной машинке я бы все-таки не рекомендовал. А вот если код/скрипты/конфиги на удаленных машинках писать -- идеально.

 

 

Парни, есть массив из N значений от 0 до 1000 с неуникальными данными. Нужно байнари серчем найти все вхождения числа Х. У меня вариант только делить массив на 2 пока не попадется первый раз число Х, а потом по оставшемуся массиву проходится форичем пока значения ==Х. Есть какой-то способ избавиться от этого форича? У меня ощущение что это кривое решение.

я совсем не из вашей сферы, гуманитарий вобщем.

уточни пожалуйста, что такое неуникальные данные?

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

 

 

и массив отсартирован уже

 

самое главное забыл в начале сказать

а то я думаю что за байнарисерч на рандомных данных когда это про отсортированный

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

 

 

 

Парни, есть массив из N значений от 0 до 1000 с неуникальными данными. Нужно байнари серчем найти все вхождения числа Х. У меня вариант только делить массив на 2 пока не попадется первый раз число Х, а потом по оставшемуся массиву проходится форичем пока значения ==Х. Есть какой-то способ избавиться от этого форича? У меня ощущение что это кривое решение.

я совсем не из вашей сферы, гуманитарий вобщем.

уточни пожалуйста, что такое неуникальные данные?

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

 

 

и массив отсартирован уже

 

самое главное забыл в начале сказать

а то я думаю что за байнарисерч на рандомных данных когда это про отсортированный

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

 

Уже представил, как это перекладывается на код; выглядит костыльненько!

Вообще во всех нормальных языках должны быть функции lower_bound и upper_bound. С их помощью и нужно искать левую/правую границу за логарифм.

Если же мы "на собеседовании" и нужно реализовать сами эти функции, то все тоже очень просто -- их код в нормальной реализации совпадает с точностью до одного if'а, в случае lower_bound сравниваем "меньше ли текущее значение, чем искомое" (т.е. if nums < targetValue), а в случае upper_bound -- наоборот (if nums >= targetValue) и в случае true левая граница текущего интервала двигается на серединку, иначе правая.

 

 

 

 

Парни, есть массив из N значений от 0 до 1000 с неуникальными данными. Нужно байнари серчем найти все вхождения числа Х. У меня вариант только делить массив на 2 пока не попадется первый раз число Х, а потом по оставшемуся массиву проходится форичем пока значения ==Х. Есть какой-то способ избавиться от этого форича? У меня ощущение что это кривое решение.

я совсем не из вашей сферы, гуманитарий вобщем.

уточни пожалуйста, что такое неуникальные данные?

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

 

 

и массив отсартирован уже

 

самое главное забыл в начале сказать

а то я думаю что за байнарисерч на рандомных данных когда это про отсортированный

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

 

Уже представил, как это перекладывается на код; выглядит костыльненько!

 

Вообще во всех нормальных языках должны быть функции lower_bound и upper_bound. С их помощью и нужно искать левую/правую границу за логарифм.

 

Если же мы "на собеседовании" и нужно реализовать сами эти функции, то все тоже очень просто -- их код в нормальной реализации совпадает с точностью до одного if'а, в случае lower_bound сравниваем "меньше ли текущее значение, чем искомое" (т.е. if nums < targetValue), а в случае upper_bound -- наоборот (if nums >= targetValue) и в случае true левая граница текущего интервала двигается на серединку, иначе правая.

 

можешь навесить на это все красивый фасад

ты смотрел как реализован lower_bound  ?

суть алгоритма от фасада не меняется

вообще алгоритм не про костыльность а про перформанс

Вот тут про костыльность немного не соглашусь. Это ж задачка с литкода вроде?

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

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

ты смотрел как реализован lower_bound  ?

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

Вот тут про костыльность немного не соглашусь. Это ж задачка с литкода вроде?

 

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

 

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

 

 

 

ты смотрел как реализован lower_bound  ?

 

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

ты помоему перепутал что-то

глуп тот кто на собес дает задачку на алгоритм а смотрит на "качество кода"

а не тот кто решил задачку на алгоритм сконцентрировавшись на скорости/оптимальности и забив на качество кода

 

Вот тут про костыльность немного не соглашусь. Это ж задачка с литкода вроде?

 

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

 

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

 

 

 

ты смотрел как реализован lower_bound  ?

 

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

ты помоему перепутал что-то

глуп тот кто на собес дает задачку на алгоритм а смотрит на "качество кода"

а не тот кто решил задачку на алгоритм сконцентрировавшись на скорости/оптимальности и забив на качество кода

 

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

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

Но да, с точки зрения большинства всякие "собеседования в яндексе/гугле" это что-то нереально сложное. Но именно так они и работают.

в чем профит от вима, научите плс?

jquery с вимом, ебать))

vim нужен в основном когда у тебя из интерфейса только консоль. например прочитать/отредачить файл на серваке и т.п.

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

Ну скриптики сам редачу в виме. Без иде это пиздец конечно ))

Если скрипты, то в midnight commander лучше редактор, как по мне.