Какие алгоритмы нужны в наше время?

Добрый вечер...вот вчера сидя за написанием «Волнового алгоритма » я задумался....а какие алгоритмы нужны в наше время(какими вы пользуетесь и в какой области их переменяете). Какие бы посоветовали изучить как базовые...? Сейчас смогу реализовать два базовых
-Сортировку(Пузырьком).
-Поиск(Бинарный).
Какими этот список маленький список стоит добавить

👍НравитсяПонравилось0
В избранноеВ избранном0
LinkedIn

Лучшие комментарии пропустить

А сортировать-то все равно будешь с помощью

order by
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

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

Алгоритмы и примитивы многопоточных вычислений

Что нужно знать из алгоритмов:
1. Применимость алгоритма к задаче, тоесть какую задачу он может решить.
2. Его сложность, чтобы выбрать оптимальный для задачи
3. Где его найти (википедии часто достаточно), чтобы можно было разобраться и реализовать, когда нет в библиотечных.

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

PS
Есть задачи, где вообще знание алгоритмов может не понадобится, типа сайтов визиток на php. Ну и этих задач на редкость много.

Из личного опыта. Знать алгоритмы на изусть это плохая идея, я за 5 лет мехмата стока всего имплементил на лабах и др. что просто месиво в голове и к 5 курсу я ни один из них не помнил. Возьмите книжку «Алгоритмы и структуры данных» проделайте все возможные алгоритмы, особенно с деревьями, а потом забейте и забудьте. Я 6 лет как программист, а вот недавно мне пришлось вспомнить курс линейной алгебры. Последний раз я этот курс слушал в 2002-2003 тоесть 10 лет назад, а ведь вспомнил все, шельма! (правда чуть-чуть гуглил). Если вам интересна данная область я бы вам советовал браться за дискретную математику и за численные методы. Но и это вам в работе тоже не пригодится, потому что если вдруг вы решите heap-sort сами написать вместо того чтобы использовать стандартную либо, то в лучшем случае вам тим-лид даст по голове :)

линейной алгебры

Это прекрасный раздел математики. Особенно для графики. Хотя да, как говорится, делить алгебру на линейную и нелинейную, как делить Вселенную на бананы и не бананы. Зато с практической точки зрения полезно

Почему же? Вполне логично отделить коров от минотавров и сначала разобраться с коровами, тоесть с объектами которые описываются линейными уравнениями :) В качестве минотавров в институте взяты кривые второго порядка и их исследуют отдельно и ведь у этих кривых применение в архитектуре, физике колосальное применение, математике затем и поделена на разделы которые при ближайшем рассмотрении потом тесно переплетаются.

Долго тут не был. И смотрю тут многие стали пинать) Ну ведь есть список базовых. Как сортировка, поиск ...
Ведь для каждой отросли свои, связанные с спецификой работы. Согласитесь?
К примеру для Gamedev(Алгоритмы поиска пути, трассировки).

У веба WEB тоже своя ниша есть. Конечно уйма алгоритмов есть на Вики, которые можно реализовать ..Ну ведь есть которые вы используете постоянно вот и стало интересно .

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

У меня такое впечатление, что я знаю место вашего обучения вплоть до преподавателя)

Возьмите стандартный курс «алгоритмы и структуры данных» приличного американского вуза и книгу его дублирующую, например, Майкла Гудрича, название не уточняю)

Мне показалась что здесь, утрирую, аналогия с вопросом:

... окончил кулинарный техникум... Вот задумался, а какие блюда нужны в наше время? Сейчас я могу:
— печь блины
— заваривать кофе
— ???
дополните список!
_____________________

:))

Подскажут одно и то же: научитесь их правильно готовить. Нет никаких базовых блюд. И ложки, кстати, тоже нет )))

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

Для собеседований — в зависимости от того, куда эти собеседования — набор алгоритмов может быть совершенно разный. Сортировки и всяческие строковые алгоритмы, мне кажется, спрашивают все. Графы и деревья спрашивают уже реже. А какие-то хитрые data-mining алгоритмы

вроде www.cs.uvm.edu/...gorithms-08.pdf , возможно и вобще только в крайних случаях. (мне кажется, кстати, если спрашивают — во первых можно ответить и неверно, а во вторых это мега удача и я бы считал что уже меня взяли. )

математику то же не собеседовании не спрашивают (ну почти). а историю и подавно.

зачем их в ВУЗах учат?

Не могли бы Вы немного развернуть вопрос: Вам не нравится, что Вас учили истории в ВУЗЕ, либо Вы считаете что, тот факт, что истории учат в ВУЗаХ как-то противоречит моему мнению, что знание алгоритмов это птичий язык для собеседований при приёме на работу?

мне все нравится. мой коментарий был по-поводу:

В реальной жизни Вам возможно вобще никаких алгоритмов не понадобится

Если Вас интересует моё, почему в вузах учат алгоритмы, когда они возможно в жизни не понадобятся, то я склоняюсь к теории «икринок» — рыбки мечут миллионы икринок, чётко понимая, что в рыбки вырастет едва ли не тысячные доли процента.

Это что касается советских вузов, конечно — это когда собственно Вузы учат а не люди учатся (и выбирают что учить) в Вузах.

студенты же, когда выбирают что учить — чаще руководствуются (вернее, я подозреваю, что руководствуются) маржинальной полезностью сигнала работодателю о том, что они это выучили. то есть, человек который в здравом уме выбирают историю в качестве предмета в Вузе — вряд ли думает стать историком (в лоттерею выиграть легче) — а скорее думает, что рассуждения об истории Рима помогут ему в собеседовании на должность ЕйчАра или ещё чего.

Собственно как и все страшные PhD в high energy physics из MIT, работающие в финансах должны были понимать перспективы применения оной физики ещё при поступлении.

Так уж получилось, что птичий язык или сигнал для программистов — это алгоритмы и простые програмки переворота строки. Вполне могла бы быть математика или ещё что-то, но так уж получилось, что это алгоритмы.

У вас как то нет четкого message что вы хотите сказать

> какие-то хитрые data-mining алгоритмы

Если проект на них специализируется, то будут спрашивать обязательно.

А если проект обычный, «формошлёперский», то спрашивать не будут. А если будут, то просто так.

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

Заучивать алгоритмы сортировки/поисканет никакого смысла. В подавляющем большинстве случаев вы будете использовать для сортировки и поиска стандартную библиотеку того языка на котором пишете, ну или order by о котором тут говорили.

На мой взгляд достаточно понять принципы работы этих алгоритмов и структур данных, их преимущества/недостатки на разных объемах данных и т.д. Но заучивать конкретные реализации нет никакого смысла. Если вы будете постоянно его использовать — и так запомнится. А если не будете — сколько не учите, все равно забудется, как и любые знания, которые не находят применения.

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

Заучивать — нет.
А написать и отладить — надо, для того чтобы понять

принципы работы этих алгоритмов и структур данных

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

Из часто попадающегося еще матрицы, поиск экстремумов, интерполяция-аппроксимация, FFT — но это, скорее, специфика моих проектов.

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

Ну и получают они посему именно, как отечественные суперпрограммисты (т.е., на уровне индусов, каковыми и являюцца).

Чтение и решение задач из Кнута и CLRS хорошо развивает мозги, что не будет лишним для разработчика в любом случае :)

Вы уже много решили задач из Кнута и CLRS?

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

Книга достаточно небольшая и простая, порог входа минимальный.

Поиска денег,возможности_свалить, высокооплачиваемой работы. Желательно, за время О(log n) :))))

Желательно, за время О(log n) :))))

Как там успехи в работе диджеем в аквапарке?

А сортировать-то все равно будешь с помощью

order by
Это если всю жизнь говносайтеги клепать, а вот некоторые и ядро разрабатывают, которое это

order by

и реализует.

А почему нельзя сказать «делать mission critical сайты» и "«клепать гавнобазки»?

делать mission critical сайты

Можно сказать, только там алгоритмы как раз и нужны

клепать гавнобазки

На гавнобазки нет спроса. На говнасайтики а — ля хоумпейдж Задрищенской фирмы по торговле насосами спрос имеется

Можно сказать, только там алгоритмы как раз и нужны

например какие?

На гавнобазки нет спроса. На говнасайтики а — ля хоумпейдж Задрищенской фирмы по торговле насосами спрос имеется

Тем не менее их уже наплодили выше крыши и продолжают плодить.

например какие?

Оптимизация и поиск, в основном.

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

А, понятно, а про нагруженные сайты просто вбросил стало быть.

а вот некоторые и ядро разрабатывают

На дотнете, поди, разрабатывают :)

На дотнете, поди, разрабатывают :)

На дотНете только распознавание изображений. :)

А чем плох? просто интересно

А чем плох?

А кто говорил что плох?

На дотНете только распознавание изображений. :)

звучало как сарказм в ответ на

а вот некоторые и ядро разрабатывают

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

звучало как сарказм в ответ на

Это и был сарказм, но в ответ на dou.ua/...ic/6447/#256493

А чем плох? просто интересно

плох некроссплатформенностью, и как результат намного меньшим рынком покупателей БД по сравнению с той же джавой.

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

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

это да, но серверный рынок и венде (МСу) бабло приносит, так что опять же это вопрос к маркетологам

en.wikipedia.org/...systems#Servers

по revenue винда вроде не плохо рынок держит

Но ее скл сервер нормально заруливается ораклом и дб2, и думаю частично из-за их кроссплатформенности.

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

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

А если это ENTERPRISE SCALABLE ROBOUST проект на миллионы строк кода? Который работает в облаке с бд оракл за тысячи долларов? Это дотнетчики только гoвносайты и клепают да формошлепствуют.

Это дотнетчики только гoвносайты и клепают да формошлепствуют.

Вы недооцениваете пхпшников, питонерастов и рубироидов :)

комментарий профессионала

Эм... Без обид, но по мойму батхёрт скорее у тебя, к тому же перманентный и вялотекущий.

Количество разработчиков которые реализуют всякие order by по сравнению с количество разработчиков использующих всякие order by и sort() настолько исчезающе мало, что им смело можно пренебречь.

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

-Я бы сверху еще рекомендовал использовать чистый си.

После того как вы реализуете работающую такую игру или две — я вас поздравляю, вам предстоит забыть все что вы зделали, и занятся наконец «настоящим» программированием =) Единственное что вам может реально пригодится это эссенция размышления над проблемой, и поиски ее устранения, отладки итд.

Ужасный бред. Просто в геймдеве, с использованием гугла во всю заняться есть чем. 100% инфа

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

Я когда то делал Тетрис на Турбо-Паскале, с его же графической библиотекой, именно так, как вы советуете. Мне это не дало ничего, кроме закрытой сессии.

Именно поэтому я и написал

вам предстоит забыть все что вы зделали, и занятся наконец «настоящим» программированием =) Единственное что вам может реально пригодится это эссенция размышления над проблемой, и поиски ее устранения, отладки итд.

А как был реализован — поворот фигур?

Как пересоздание объекта. У меня там разные положения воспринимались как разные фигуры.

Не партесь над производительностью, эфективностью,

Не ну это вы зря такое советуете. Это хорошая подзадача в любой задаче

Моя практика показывает, что новичкам поначалу лутше таки не парится, а фокусироватся именно на «getting things done». А уже после некоторой набивки опытом, начать изучать вопросы производительности, эффективности, поддерживаемости, архитектуры, итд.

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

piccy.info/...7beac8f39/orig
piccy.info/...ccfd1a0f9/orig
piccy.info/...5ed090a3b/orig
piccy.info/...c50bf2fa6/orig
piccy.info/...200b9ce02/orig

piccy.info/...eb1c32ef5/orig

Подскажите, пожалуйста, обязательные главы подлежащие прочтению. Для вэб/бизнес разработки.

Страницы с 13 по 19.

Какие бы посоветовали изучить как базовые...? Сейчас смогу реализовать два базовых

Изучать (и знать) надо все (или как можно больше)! При том не только стандартные, а все к которым дотянетесь.

Но «знать» не значит «уметь реализовать» или тем более «реализовывать для реальных проектов».

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

Кроме знания структур и штатного метода их применения полезно бы знать различные читы, которые помогают в конкретных случаях, например как соединить два иммутабельных списка за O(1)

например как соединить два иммутабельных списка за O(1)

Поведайте, будет интересно. Как можно чего-то соединить даже не просматривая.

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

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

O(n)?

Здаетсо мне что речь таки о списке списков (после обхода одного, обходить второй).

Почему O(n) если список хранит указатель на первый и последний элемент?

Почему O(n) если список хранит указатель на первый и последний элемент?

2) Наличие указателя на последний элемент — это уже серьезное ограничение, далеко не у каждого списка такой есть.

1)

соединить два иммутабельных списка

Списки не изменяемые. Хотел написать O(n+k), но не написал.

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

Даже если бы они были изменяемыми, такой финт чреват последствиями: например, вы добавили элемент в первый список, а он добавился во второй.

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

2) Наличие указателя на последний элемент — это уже серьезное ограничение, далеко не у каждого списка такой есть.

А в чем ограничение O(1) памяти, O(1) добавление нового элемента в конец?

А в чем ограничение O(1) памяти

Кто говорил про O(1) по памяти?

Если честно я не понял ваш комментарий, поясните, пожалуйста.

В чем реализация списка с указателем на последний элемент слздает серьезные ограничения? вроде как и памяти не много и CPU на это тратиться и структурно ничего сложного

В чем реализация списка с указателем на последний элемент слздает серьезные ограничения?

1) АПИ списка должно содержать соответствующий метод.

2) Сложность этого метода должна быть O(1)

зачем апи? зачем метод? какая сложность? хранить еще один указатель? вроде ж во времена гигабайтов живем что бы на 8 байт (ато и меньше) не жлобиться

class DOUList(object):
def __init__(self):
self.begin = None

self.end = None

def Add(self, i):
if self.begin is None:
self.begin = i
else:
self.end.next = i

self.end = i

зачем апи? зачем метод? какая сложность? хранить еще один указатель?

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

Что делать? Заморозить таск пока чуваки не подфиксят свою либу?

Так а чем использование прокcи обьекта не подходит?

Так а чем использование прокри обьекта не подходит?

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

Нет, а это требуется в исходной задаче(слить два списка)?

Нет, а это требуется в исходной задаче(слить два списка)?

Ой, даже и не знаю:

как соединить два иммутабельных списка за O(1)

Ой, даже и не знаю:

И что не так? Зачем для соединения списков с помощью прокси доступ к последним элементам?

Зачем для соединения списков с помощью прокси доступ к последним элементам?

За тем что надо читать всю ветку :)

Я четал. так што нитак?

А вы попробуйте прочИтать ... внимательнее? :)

А может ты попробуешь мозжечек поднапрячь лучше и попытаться понять то о чем я пишу?

попытаться понять то о чем я пишу?

А что тут понимать, кто-то не осилил прочитать первые 4 коммента ветки.

ну так я ж говорю, поднапряги мозжечек и прочти наконец

Это обычная практика так как кушать не просит, а вставка в конец константа, посмотрите например www.docjar.com/...dList.java.html

посмотрите например www.docjar.com/...dList.java.html

Там еще такое есть:

www.docjar.com/.../util/List.html

Это обычная практика так как кушать не просит, а вставка в конец константа

А какие затраты памяти по сравнению с другими списками? А какая сложность (скорость) других операций?

Кстати, если пользоваться ЛинкедЛистом, то сложность все равно линейная, так как просто присоединять весь список не безопасно (и добавлять вы можете только по одному).

Повторяю еще раз:

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

Там нет никакого self.end и даже нет метода который его может посчитать внутри объекта.

Итого вы решили задачу, для случая когда есть указатель на последний элемент и дальнейшее поведение исходных списков не важно для выполнения программы. А это где-то “в околі нуля”.

The List interface provides four methods for positional (indexed) access to list elements. Lists (like Java arrays) are zero based. Note that these operations may execute in time proportional to the index value for some implementations (the LinkedList class, for example). Thus, iterating over the elements in a list is typically preferable to indexing through it if the caller does not know the implementation.

Вы уверены что нашли что-то правильное?

en.wikipedia.org/...ract_data_type

Lists are typically implemented either as linked lists (either singly or doubly linked) or as arrays, usually variable length or dynamic arrays.

The standard way of implementing lists, originating with the programming language Lisp, is to have each element of the list contain both its value and a pointer indicating the location of the next element in the list. This results in either a linked list or a tree, depending on whether the list has nested sublists. Some older Lisp implementations (such as the Lisp implementation of the Symbolics 3600) also supported “compressed lists” (using CDR coding) which had a special internal representation (invisible to the user). Lists can be manipulated using iteration or recursion. The former is often preferred in imperative programming languages, while the latter is the norm in functional languages.

Lists can be implemented as self-balancing binary search trees holding index-value pairs, providing equal-time access to any element (e.g. all residing in the fringe, and internal nodes storing the right-most child’s index, used to guide the search), taking the time logarithmic in the list’s size, but as long as it doesn’t change much will provide the illusion of random access and enable swap, prefix and append operations in logarithmic time as well.

Я не джавист, но List это интерефейс, причем тут он, при том это интерфейс который как раз и реализует конкретная реализация LinkedList,

А какие затраты памяти по сравнению с другими списками? А какая сложность (скорость) других операций?

в обиходе что бы не путать часто под list подразумевают LinkedList а индексированые штуки array

К слову linked list быстре всего смержит 2 списка так как в одну операцию конечный элемент направиться на первый нового списка, что тут небезопасного и почему нужно итеративно делать пожалуйста обьясните?

а вот array-style структуры как раз могут потребовать больше чем O(1) когда прийдет пере-выделять память и копировать элементы что бы сохранять индекс, или использовать гибридную структуру аля прокси, которую вам тут привели

Итого вы решили задачу, для случая когда есть указатель на последний элемент и дальнейшее поведение исходных списков не важно для выполнения программы. А это где-то “в околі нуля”.

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

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

например как соединить два иммутабельных списка за O(1)

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

en.wikipedia.org/....ract_data_type

Прекрасная ссылка. Обратите внимание на «Abstract definition». Где там сказано что есть указатель на последний элемент? Это оптимизация которую могут добавить, а могут и не добавить.

что тут небезопасного и почему нужно итеративно делать пожалуйста обьясните?

Так писал вроде бы:

вы добавили элемент в первый список, а он добавился во второй.

Уточнение: в конец первого списка.

immutable в структурах обычно относиться к даным, а не структуре

Дайте определение понятия «структура», пожалуйста?

Везде где встречал слово «immutable» в контексте коллекций, оно подразумевало: невозможность добавить/удалить/изменить позицию (если позиция имеет значение) элемента коллекции.

Прекрасная ссылка. Обратите внимание на «Abstract definition». Где там сказано что есть указатель на последний элемент? Это оптимизация которую могут добавить, а могут и не добавить.

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

вы добавили элемент в первый список, а он добавился во второй.

Уточнение: в конец первого списка.

def BogdanMerge(listA, listB):
listA.end.next = listB.begin
listA.end = listB.end

return listA

в чем проблема? все последующие будут добавляться в конец B?

Везде где встречал слово «immutable» в контексте коллекций, оно подразумевало: невозможность добавить/удалить/изменить позицию (если позиция имеет значение) элемента коллекции

Отлично в вашей интерпретации стоило бы тогда просто ответить на мое высказывание — нельзя так как нельзя менять исходные структуры

Обратите внимание на «Abstract definition». Где там сказано что есть указатель на последний элемент?

Хм, а вы не знаете разницу между интерфейсом и реализацией? Кстати если речь идет про задачки на собеседование то там обычно оговариваеться какая реализация, если реальная жизнь описываеться доками — я вам привел пример Java, вот вам пример реаизаци у конкурента: www.coderprofile.com/...inked-list-in-c

на сегодня для связного списка хранить указатель на конец это нормальное явление и даже если этого нет, всегда можно наследованием исправить, но опять же задача в постановке:

например как соединить два иммутабельных списка за O(1)

Очень широкая в интерпретации, и в вашей интерпретации мое предположение работать не будет — и это ок :) тут нужно либо условие уточнять и тогда решать либо идти спать :)

def BogdanMerge(listA, listB):
listA.end.next = listB.begin
listA.end = listB.end
return listA

в чем проблема? все последующие будут добавляться в конец B?

Проблема такая:

listA = [1, 2, 3];
listB = [4, 5, 6];
BogdanMerge(listA, listB);
listA.Add(7);

Вопрос: Чему равен listB.end ? Что будет после итерации по listB?
Подозрение:
1) listB.end будет указывать на «6» (скорее всего),
2) но при итерации listB == [4, 5, 6, 7].

Даже если 1 не верно, получаем очень веселый сайд-эффект. Если 1 верно — получаем битые данные.

Хм, а вы не знаете разницу между интерфейсом и реализацией?

Я знаю, а вы? При построении алгоритма можно опираться ТОЛЬКО на интерфейс ибо реализация может поменяться, то есть ваше предположение про ссылку на последний элемент — очень не предсказуемо.

тут нужно либо условие уточнять и тогда решать

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

Вопрос: Чему равен listB.end ? Что будет после итерации по listB?

Подозрение:

На каком мне языке это написать:

Отлично в вашей интерпретации стоило бы тогда просто ответить на мое высказывание — нельзя так как нельзя менять исходные структуры

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

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

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

Угу, только структура данных не персистентна. Тоесть список поменял состояние. С иммутабельным списком оба списка будут сосуществовать. И я не понимаю к чему обсуждение о конце списка, это не поможет в классическом (value, next) списке, в котором при условии иммутабельности списка прийдется пересоздать весь список

Итак снова :)

Был вопрос на тему почему не будет все работать на шару — так себе самый простой вариант и дабы узнать ограничения и понять из-за чего напрягаться и в какую сторону смотреть, после чего началось обсуджение списков которых хранят указатель на хвост, на сколько это сложно с точки зрения реализации и ресурсов системы, когда товарищь Богдан уточнил что задача о списках которые не меняються и вообще в авбстрактной реализации я ответил — аа все ок не будет работать и все! так как на тот момент рабочий вариант с прокси уже был озвучен, что нового вы хотите обсудить?

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

Да ничего, все ок )

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

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

jr dev, ваш ответ не может быть принят. на то есть как минимум две причины:
— списки неизменяемые

— ваши списки всегда знают свой хвост.

Короче ... никакого отношения к алгоритмам это не имеет ;)

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

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

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

Создаешь новый proxy обьект, у которого две ссылки на исходные списки, в чем проблема?

Тобиш, там помимо «структуры данных», еще и «ООП» с его полиморфизмом идет ;-)

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

осталось выяснить почему в скале ::: не реализовано через вью.

Отличный вопрос. Но мне кажется они не хотят получить структуру в памяти странной формы после нетривиального алгоритма. Согласно презентации ребят из Oracle не помню какой конференции в JVM есть оптимизация если структуры следуют паттерну (value,next), она их перепаковывает их подряд в памяти для лучшей утилизации кеша при итерации.

++ для двух view будет третьим view агрегирующим два других за константное время без копирования всего контента.

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

например как соединить

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

ни про какое соединение вы не подразумеваете в вашей задаче. еще и козыряете O(1). к чему оно тут вообще?

как представить два объекта типа лист в виде одного.

А может тебе ещё дать ключ от квартиры, где деньги лежат? ©

Та не, у меня свой есть. Зачем мне еще?

О принципе подстановки Лискова слышали? Можно унаследоваться от списка и вернуть таким образом все равно список

О принципе подстановки Лискова слышали?

Палишсо: Лисковой :)

Только английское название слышал. Как перевел так и перевел. Спасибо)

она вроде Барбара. Да и вообще я бы не склонял иностранные фамилии.

разговор не об этом. еще раз — первоначально вы говорили «соединить». а оказывается подразумевалось некое логическое или семантическое представление, что может быть разным в разных парадигмах. и опять таки — к чему было писать про O(1)?

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

Оказывается что представления тоже на практике работают и никто от этого не страдает. И за O(1). Или определить враппер имеет другую сложность?

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

А вот если в проекте действительно нужны «алгоритмы», то «базовыми» там не обойтись.

Смысл в том что бы логику разработать...

Это не отменяет необходимости понимания того, какой алгоритм будет наиболее эффективен (если вообще работоспособен) в той или иной ситуации.

Это понимание не появится, если человек просто выучит несколько алгоритмов из разряда «сортировки пузырьком».

зачем что-то добавлять. берешь книжку и читаешь. благо книг валом.

те кто использует пакет

java.util.*

зная это или нет используют и структуры данных (list, hashmap, heap, tree, etc.) и алгоритмы (sort, binary search, etc.)

Какими этот список маленький список стоит добавить

а вы с какой целью интересуетесь ©

Цель саморазвитие....мне ведь только 21 и есть желание поломать стереотип)))))что нету senior в 23)

Нынешние 23-х летние синьйоры не от того что они алгоритмы сортировки знают ;-)

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

Я не помню, чтобы мне нужны были алгоритмы сортировок в работе.

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

Я сейчас пользуюсь алгоритмами для обработки графики.

Деревья в основном. Но тут много зависит от специфики деятельности.

PS: долой пузырёк!

ну я если надо к быструю реализую, и Шелла)))или просто vector.sort();

ну я если надо к быструю реализую, и Шелла)))или просто vector.sort();
В реальном мире вам надо использовать стд_либа_вашего_языка.сотр(), а за любое «я реализую» в 99% случаев надо бить по рукам.
в 98% ;-)

2% теоретически приходится на хитроебские структуры данных написанные «индусами» гдето в легаси коде, которые стандартными средствами ну никак не отсортируеш :-)

Ну если в C# (это не попытка возобновления холивара), то можно через LINQ отсортировать что угодно.

через LINQ отсортировать что угодно.

Ок. Имеем связный список, который не реализует стандартные интерфейсы, а только самопридуманые. То есть вместо: IQueryable (вроде он надо для работы LINQ) и IEnumerable, используются MyIQueryable и MyIEnumerable или вообще ничего.

Как тут поможет LINQ?

Всё, вопрос снят, вы правы.

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

можно унаследовать самописный класс

И всегда можно унаследовать?

Говнокодеры описываемого вами маштаба не знают про sealed. Но даже если и так — можно создать класс наследующий ИЭнумерабл и инкапсулирующий самописный.

Но даже если и так — можно создать класс наслудеющий ИЭнумерабл и инкапсулирующий самописный.

Как уже писал:

dou.ua/...ic/6447/#256603

Второй момент, но он очень редкий (даже с ходу не могу привести пример):

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

А то, что вы писали прокатит, для маловменяемой структуры, сортирующейся по нескольким правилам и параметрам?

А что касается второго момента — таки да, но для ПО, для которого критично быстродействие, Жаба и Шарп — не лучший выбор.

А то, что вы писали прокатит, для маловменяемой структуры, сортирующейся по нескольким правилам и параметрам?

А почему не должно? Есть подозрение что линку вполне вызывает тот же сорт, просто с другим синтаксисом.

Можно джавовский пример? Скажем имеем структуру с полями а и b, сортировать по a, если a >= 0, сортировать по b, если а < 0.

Просто интерестно, как это выглядит.

Просто интерестно, как это выглядит.

Есть подозрение что так же как и в шарпе. :)

Скажем имеем структуру с полями а и b, сортировать по a, если a >= 0, сортировать по b, если а < 0.

class Obj {
public int a;
public int b;
}

class C implements Comparator<obj> {
@Override 
public int compare(final Obj o1, final Obj o2) {
if (o1.a >= 0) {
Integer.valueOf(o1.b).compareTo(o2.b);
}
return Integer.valueOf(o1.a).compareTo(o2.a);
}
}

Так можно (IComparer) и нужно, если поиск юзается много раз, но одиночный случай удобнее ЛИНКом.

но одиночный случай удобнее ЛИНКом.

Мы (в моем лице) говоили про функционал, а не про удобство:

через LINQ отсортировать что угодно.

Если

Но даже если и так — можно создать класс наследующий ИЭнумерабл и инкапсулирующий самописный.

То мы сможем применить ЛИНК для такого случая. Но это будет уродливее чем просто реализация ИКомпэрэбл.

А что касается второго момента — таки да, но для ПО, для которого критично быстродействие, Жаба и Шарп — не лучший выбор.

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

Честно говоря, я с такими ситуациями не сталкивался.

Та я сам сталкивался только один раз, И это был «страшный» легаси код.

ха! адаптер напишут. а потом отсортируют через linq!

ха! адаптер напишут. а потом отсортируют через linq!

Заворачиваем в коллекшн и применяем стандартный метод сорт, и не надо ни какого линку.

это не по-пацански. LINQ круче!

Привести самописный интерфейс к IEnumerble и все

Подписаться на комментарии