Я крыс пройду собеседование на 5

stm6692945

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

tokuchu

ява2се

Зачем оно?

stm6692945

Вот такие вопросы меня просто бесят .

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

cinot

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

как технически работает контейнер сервлетов в режиме веб-сервера?

hvn1967

это не se

stm6692945

Я же сказал только "се"

danilov

> Спрашивайте что бы вы спросили на собеседование по ява2се
Что бы ты спросил на собеседование по ява2се?

stm6692945

Мой первый вопрос был бы :
хуи сосеш

katrin2201

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

Papazyan

ява2се

Назови значение 105-го байта в файле java.exe.

kokoc88

Назови значение 105-го байта в файле java.exe

У меня пол года в Java SE не было такого файла. :cool:

stm6692945

А вы где , может зайду если буду рядом

katrin2201

павелецкая 2с2

stm6692945

Не знаю про 105

bav46

пробел будет как и во ввсех экзешниках в 32 битной системе

VitMix

Почти всегда задаю такую задачу: приведи пример ситуации, в которой LinkedList подходит значительно лучше, чем ArrayList. "Значительно" обозначает, что разница должна быть на порядки, а не на проценты.

stm6692945

Не знаю , в какой и почему

Serab

четыре

kill-still

так, "Чисто поржать" ?

zorin29

Не знаю , в какой и почему

Сильно уже прокачался?

Как сделать утечку памяти в твоей программе?

katrin2201

Да не, на самом деле просто интересно на человека посмотреть.
Оборжались мы тут всем отделом летом, когда две вакансии было открыто... Ржать, кстати, обычно не хочется. просто грустно ='(

stm6692945

Оборжались мы тут всем отделом летом, когда две вакансии было открыто

вот она вся правда о синьерах

enochka1145

// я поотвечаю заодно и немного качнусь
Может ли статический вложенный класс обратиться к членам данных включающего класса?
(Этот вопрос задали 5 лет назад мне.)

enochka1145

Есть ли в Java невиртуальные функции-члены?

stm6692945

нет

stm6692945

я не знаю что такое невиртуальные
и чо такое функции члены
ты после давай правильные ответы плизз

Serab

наверняка наебка в том, что конструкторы типа не виртуальные :grin:

ну еще статические функции лол

enochka1145

Не только конструкторы, ещё и приватные методы.

enochka1145

// // Может ли статический вложенный класс обратиться к членам данных включающего класса?
// нет
Ответ неверный.

stm6692945

ну значит да

enochka1145

А вообще, почему бы не раздобыть какие-нибудь экзамены на сертификат Sun по Java? Думаю, было бы очень полезно.

enochka1145

// ну значит да
ответ тоже неверный.
А это, знаете ли, основы. Я тут не спрашиваю про атомарность работы с Integer64 или почему сборщик мусора может не собрать весь мусор, что тоже, в общем-то, тривиально.

stm6692945

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

zorin29

крыс, ты мне напоминаешь одного моего однокурсника, которого на экзамене по уравнениям мат.физики "завалили" вопросом "что такое комплексное сопряжение".
Ты хочешь, чтобы тебе задавали вопросы по синтаксису языка? Так это никому не интересно, тебе IDE подскажет синтаксис все равно. Вот и спрашивают с тебя программирование вообще, особенности java-машины и отличия языка Java от других ОО-языков.
Функция-член - C++ - название для "метода класса", в противовес функциям (скажем, main. В Java любая функция - это функция-член.

zorin29

Что такое полиморфизм?
Есть ли в Java множественное наследование? А если нет, то как мне его реализовать?
Как в в многопоточной Java-программе сделать эксклюзивный доступ к разделяемому ресурсу?

Serab

хм, любопытно? Вон, Саттер грит, что в плюсах вообще не надо открытые методы делать виртуальными. Понятно, что это дрочерский заеб для расширяемости во все дыры, но все же, в джаве нельзя сделать private-метод виртуальным? Иногда этого хочется (template method)

stm6692945

да... да идите вы все нахуй

enochka1145

// джаве нельзя сделать private-метод виртуальным?
Или private, или виртуальным. Если нужна и виртуальность, и защита от внешнего мира, есть protected.

enochka1145

// и да, какой ответ правильный там и почему
А Java взботнуть не пробовал?

А бошку включить?

danilov

Да, но я не знаю, пользуется ли NVI и какие оно даёт плюсы.
private-метод виртуальным сделать нельзя. Но мне, например, как-то не приходит в голову, зачем. А вот приватное наследование очень бы помогло.

danilov

> А Java взботнуть не пробовал? А бошку включить?
Ну вот я вроде знаю java, но вопроса не понял.
Можно создать экземпляр класса и использовать приватные поля, это значит да или нет?
А без экземпляра, конечно, нет. В общем странный вопрос, сильно искусственный и переусложнённый (или там всё гораздо сложнее?).

enochka1145

// А вот приватное наследование очень бы помогло.
Кому? Чем? За всё моё время в программировании не помню не одного нормального примера, только один свой, за который мне стыдно

. С вероятностью 99.99% "приватное наследование" означает "плохой дизайн".

Serab

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

enochka1145

// А без экземпляра, конечно, нет.
FAIL!111

danilov

Да, оно решается делегированием, но сокрытие интерфейса было бы более простым и читаемым решением.
Согласен, встречается не часто, не не всегда плохой дизайн

stm6692945

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

enochka1145

Поищи Thinking in Java (Философия Java). Для SE большего не надо.

danilov

Ну, к статическим да, может. Но по вопросу нихера не ясно, что ты хочешь.
> к членам данных включающего класса
Очень тяжело распарсить. Может задашь вопрос нормально?

Serab

ну вот и вопрос назрел (мне задавали, правда не совсем на собеседовании) и, логично, что это про плюсы, потому что там есть private-наследование. Ну так вот, собственно, и вопрос: когда оно необходимо :grin:

enochka1145

// Очень тяжело распарсить. Может задашь вопрос нормально?
Вопрос задан предельно ясно. Правильный ответ (который я и дал, обчитавшись Thinking in Java): "да, если данные-члены статические". :grin:

enochka1145

// Ну так вот, собственно, и вопрос: когда оно необходимо
На собеседовании. Сразу после важнейшего вопроса "что происходит, когда деструктор бросает исключение"?

danilov

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

stm6692945

Вкратце че это за книга "Философия Java" ?
Все просто молятся на нее. Там синтаксис и примеры из Se или вся книга расказывает о особеностях языка?

danilov

Вопрос задан не про данные-члены, а члены данных. Ты хоть сам читал, что написал.
Даже, блядь, падежи не совпали.

Serab

Ответ неверный. Ах-хахахахахаха!
Ответ как и всегда: для повторного использования. Если тебе в классе для использования необходимо переопределять виртуальные методы, то наследование необходимо, если не хочешь при этом наследовать интерфейс, надо наследоваться закрыто. Поэтому агрегирование и не проканает. В опыте такое бывало. Можно, конечно, унаследовать private-класс и его уже заагрегировать. Но ебаааать!

stm6692945

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

stm6692945

Почти всегда задаю такую задачу: приведи пример ситуации, в которой LinkedList подходит значительно лучше, чем ArrayList. "Значительно" обозначает, что разница должна быть на порядки, а не на проценты.

пиздатый вопрос, спасибо.



public class TestClass

{

    public static  void main(String[] args)

    {

        LinkedList<Integer> lin_list = new LinkedList<Integer>

        ArrayList<Integer> arr_list = new ArrayList<Integer>



        for(int i = 0; i < 11451103; i++)

        {

            int num = (intMath.random*10000000);

            lin_list.add(num);

            arr_list.add(num);

        }



        long start = System.nanoTime;

        lin_list.add(5);

        System.out.println(System.nanoTime - start);



        start = System.nanoTime;

        arr_list.add(5);

        System.out.println(System.nanoTime - start);

    }

}

output:



12800

120918308

Цимес, как можно понять, в волшебной цифре 11451103 (которую я, не парясь, подсмотрел в дебаге). На этом месте при добавлении следующей циферки arraylist дропает свой внутренний массив и создает новый, удвоенной величины и копирует туда все значения, плюс это новое, а линкедлист, как обычно добавляет элемент за О(1).
Алсо, пацаны, ответы на все ваши вопросы можно найти в гугле! Так не очень интересно!

kokoc88

Цимес, как можно понять, в волшебной цифре 11451103

Цимес поставленного автором вопроса вовсе не в этом.

stm6692945

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

Serab

наоборот, если суммарное посчитаешь, массив быстрее будет, лол!

kokoc88

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

В этих операциях LinkedList будет хуже раза в два, а то и больше.

Serab

ну, кстати, если написать свой аллокатор фиксированного размера, то может и не в два раза (потому что при перевыделении не надо будет копировать старые данные). Но дело в любом случае не в последовательном добавлении, конечно :grin:

Serab

кстати, недавно тестил realloc случайно. Он тоже догадливый, тоже пропорциональный запас делает у меня в glibc, поэтому прога, реаллочащая при каждом увеличении размера не так уж и проигрывает более хитрому варианту. Как раз раза в два, хотя должна в тысячу!

kokoc88

кстати, недавно тестил realloc случайно

Ты между его вызовами создавал-удалял объекты, которые приводят к фрагментации?

stm6692945

Да, неудача. Но с последовательным удалением вроде прокатило,



public class TestClass

{

    public static  void main(String[] args)

    {

        LinkedList<Integer> lin_list = new LinkedList<Integer>

        ArrayList<Integer> arr_list = new ArrayList<Integer>



        for(int i = 0; i < 10000000; i++)

        {

            int num = (intMath.random*10000000);

            lin_list.add(num);

            arr_list.add(num);

        }        



        long start = System.nanoTime;

        for(int i = 0; i < 10000000; i++)

        {

            lin_list.remove;

        }

        System.out.println(System.nanoTime - start);

        

        start = System.nanoTime;

        for(int i = 0; i < 10000000; i++)

        {

            arr_list.remove(i);

        }

        System.out.println(System.nanoTime - start);

    }

}

аррайлист до сих пор удаляет :grin:

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

zorin29

for(int i = 0; i < 10000000; i++)
     {
     arr_list.remove(i);
     }

В принципе, Крыс, я уже составил о тебе мнение как о программисте

Поверь мне, тебе еще рано почивать на лаврах, лучше поучись программированию еще немножко.

Serab

Ну там надо как-то хитро, потому что если выделить фиксированного размера блок, то он его при одном из первых реаллоков перепрыгнет и он (фрагментирующий блок) начнет выделяться где-то вначале. Но я с тобой согласен, если много свободной памяти, то дело не в его хитрости, а в том, что там дальше просто куча свободного места.
А потом, когда он выделяет уже отдельными mmap'ами для каждого блока, он себя не супер-хитро ведет, но тоже не совсем тривиально, начиная примерно с 483322 интов начинает удваивать, чесслово, вот прога, кстати:



#include <stdio.h>

#include <stdlib.h>



int main

{

    int *a;

    int n;

    int reservedSpace;

    int i;

    int pointerChanges;



    n = 0;

    reservedSpace = 50;

    a = (int*) malloc( reservedSpace * sizeof( int ) );



    pointerChanges = 0;



    for(i = 0; i < 10000000; ++i) {

        if( n == reservedSpace ) {

            void* aOld = a;

            a = (int*)realloc( a, (reservedSpace += 1) * sizeof( int ) );

            if( a != aOld ) {

                ++pointerChanges;

                printf( "%d, ", i );

            }

        }

        a[n] = 18;

        ++n;

    }

}

Соотв-но можно заменить reservedSpace +=1 на что-нибудь типа reservedSpace *= 2 (поэтому, собстно, так странно и написано).

stm6692945

а что тут не так?

Serab

да это просто троллинг :grin:

Serab

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

kokoc88

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

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

начиная примерно с 483322 интов начинает удваивать, чесслово,

Ну а malloc, начиная с этого места, тоже удваивает?

stm6692945

других методов удаления в аррайлисте вроде нет

Serab

Какая методика проверки?

Serab

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

Serab

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

kokoc88

Какая методика проверки?

Я не знаю, потому что не проверял... Попробуй поскладывать string различной длины между вызовами realloc. При этом желательно сохранить 3 строки в векторе, а на следующей итерации удалить среднюю, сохранив две оставшиеся до конца. Вот.

stm6692945

Ты бы не выебывался, а нормально объяснил. С конца удалять быстрее, да, но это неэквивалентные ситуации - допустим, требуется удалять именно с начала

Serab

с начала быстро не удалишь, тут уже придется программировать. Например, хранишь число удаленных с начала элементов и прибавляешь его к каждому индексу, когда накопится, скажем, та же половина, можно и на самом деле удалить, одним заходом. Опять же выйдет быстрее, чем со списком. И это если память так быстро нужна. Добавления и удаления только в начале и конце тоже лучше делать массивом, циклическую индексацию там бахнуть (пишется легко например. Списки нужны не так часто :grin:

Как раз это девочке с геологического недавно объяснял, она сама все написала :grin:

stm6692945

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

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

Serab

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

zorin29

а что тут не так?

Ну, если мне не изменяет здравый смысл, то ты удалишь все элементы с четными номерами из массива, а потом еще 5 000 000 раз сделаешь remove(x где x>arr_list.length

kokoc88

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

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

kokoc88

Ты бы не выебывался, а нормально объяснил. С конца удалять быстрее, да, но это неэквивалентные ситуации - допустим, требуется удалять именно с начала

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

Serab

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

Serab

Ты уже написал в общем-то подходящий ответ: использовать эти списки в качестве Deque

ну я вот все равно не согласен :grin:

дек на массиве все еще быстрее, если самому написать. Все же листы нужны при добавлении и/или удалении из середины или ну там вставке целого участка в середину (наверное и не писал такого никогда :grin:

)

stm6692945

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

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

Ну, если мне не изменяет здравый смысл, то ты удалишь все элементы с четными номерами из массива, а потом еще 5 000 000 раз сделаешь remove(x где x>arr_list.length

омг!

Serab

кстати

kokoc88

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

Если ты не согласен, то почитай мой пост внимательнее.
Кроме того, добавление/удаление в середине linked list имеет среднюю сложность O(N это такая же сложность, как и в массиве.

kokoc88

омг

Надо было написать remove(0)

Serab

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

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

stm6692945

Ну, если мне не изменяет здравый смысл, то ты удалишь все элементы с четными номерами из массива, а потом еще 5 000 000 раз сделаешь remove(x где x>arr_list.length

действительно, хуйня какая-то произошла

Serab

Кроме того, добавление/удаление в середине linked list имеет среднюю сложность O(N это такая же сложность, как и в массиве.

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

stm6692945

Надо было написать remove(0)

остановимся на том, что я это имел в виду

kokoc88

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

У тебя есть пример реальной задачи, когда надо добавлять в середину списка без поиска? Не высасывай из пальца какие-то нереальные ситуации, плиз. А то сейчас ты linked list посоветуешь сделать в виде списка из массивов элементов, что позволит тебе ещё быстрее искать середину. А если сделать skip list, так вообще будет логарифм.

kokoc88

правда не по последовательным адресам, что довольно существенно, но все еще не очевидно, что равноценно.

Это не равноценно. Даже при последовательном доступе LinkedList в среднем намного медленнее, особенно в языках с GC.

Serab

ну блин, у тебя есть проход линейный по последовательности, где иногда надо вставлять. Тут поиск у тебя идет сам по себе. Ну тут да, если один проход, то массив можно просто пересоздавать сразу на новом месте, но это уже «а можно сделать совсем по-другому». Или у тебя могут быть ссылки на элементы списка из какой-нибудь внешней структуры (графа, например) прямо на нужные тебе элементы списка.

Serab

Это не равноценно. Даже при последовательном доступе LinkedList намного медленнее, особенно в языках с GC.

не понял, причем тут GC, но согласен, с нормальным компилятором удаление элемента из середины массива должно быть быстрее, чем поиск по linked-list'у.

kokoc88

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

А средняя сложность никуда не идёт и остаётся O(N) :cool:

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

Это уже не структура данных linked list. Так что КПблЦ в итоге нарыл правильные ответ на вопрос автора.

Serab

А средняя сложность никуда не идёт и остаётся O(N)

хуясе! там O(N(N-1) /2) vs O(N)

kokoc88

не понял, причем тут GC

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

Serab

Это уже не структура данных linked list. Так что КПблЦ в итоге нарыл правильные ответ на вопрос автора.

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

Serab

Так что КПблЦ в итоге нарыл правильные ответ на вопрос автора.

нет, ну в некотором роде, это, конечно, ответ, но не на пять. Понятно, тупо удалять из начала лучше из linked list, чем из массива, но это плохой пример. Вот у нас в школе на двери кабинета информатики когда-то висела бумажка, на ней говорилось, что умеющий поменять значения двух переменных достоин тройки, умеющий это сделать не используя третьей достоин четверки, а знающий, когда этого делать нельзя, достоин пятерки. Так и тут, логическое удаление из начала не обязательно должно быть выражено инструкцией remove(0)

stm6692945

майк как бы имеет в виду вот эту мою цитату

Еще в интернетах пишут, что при реализации очереди линкедлист будет эффективнее

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

kokoc88

хуясе! там O(N(N-1) /2) vs O(N)

Я не понял твоей оценки O(N^2). Надо более чётко поставить задачу, ты привёл такую ситуацию: есть функция, которая принимает массив из K элементов, где K ~~ N, которые надо вставить в структуру данных LinkedList или ArrayList. Теоретически, их можно вставить в список за O(N а вставка в лоб в массив будет O(N^2 но тут любой разработчик скажет, что он создаст массив заново, потому что O(N) по памяти предпочтительнее сложности O(N^2).

Serab

нет, вставлять надо не один непрерывный кусок, а после некоторых элементов по какому-нибудь условию. Ну да, будет O(N*K) vs O(N) при лобовой реализации.

kokoc88

нет, ну в некотором роде, это, конечно, ответ, но не на пять.

Это конкретный вопрос с конкретным ответом: когда LinkedList лучше ArrayList. Это конкретные классы в JDK, с конкретной сложностью работы. Ответ про Deque/Queue (ArrayList не реализует эти интерфейсы) здесь вполне тянет на пять.
Потому с амортизацией удаление из начала ArrayList будет иметь сложность O(N ты просто поменяешь коэффициент. Да и сделать амортизацию ты можешь только в своём классе, через ArrayList это сделать не получится.
Только прежде чем писать отзыв о наборе коллекций на массивах, надо понимать, что есть ArrayDeque, который амортизирует массив с обоих концов, и работает быстрее LinkedList; но автор всё-таки спрашивал про ArrayList.

Serab

O(N^2 ты просто поменяешь коэффициент

неправда, если по настоящему удалять только когда размер уменьшился вдвое, то будет NlogN

Serab

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

Serab

Ну или склейка справа/слева двух списков — вот, но где бы это было нужно?

Serab

Теоретически, их можно вставить в список за O(N а вставка в лоб в массив будет O(N^2 но тут любой разработчик скажет, что он создаст массив заново, потому что O(N) по памяти предпочтительнее сложности O(N^2).

тут как бэ тоже создавать новый не надо, просто надо смещать сразу на K.

kokoc88

неправда, если по настоящему удалять только когда размер уменьшился вдвое, то будет NlogN

Тут весь вопрос остаётся в том, когда он уменьшился вдвое? Элементы-то тем временем продолжают добавляться в конец массива. На самом деле для O(1) тебе нужно будет сделать из ArrayList кольцевой буфер; только тогда на собеседовании тебя спросят о готовом (см. выше).

kokoc88

тут как бэ тоже создавать новый не надо, просто надо смещать сразу на K.

Согласен, но этой операции нет в ArrayList. И ещё, вроде бы он не умеет удалять целый кусок изнутри.

stm6692945

все таки как вам было тяжело без меня
пока я тут не флудил :smirk:

Serab

Ну я все-таки надеюсь, что по поводу java мне собеседоваться не придется в этой жизни :grin:

Вот именно, что кольцевой буфер (выше писал но я рассматривал сейчас модель КРЫСа — удаление из начала до упора :grin:

Serab

Согласен, но этой операции нет в ArrayList. И ещё, вроде бы он не умеет удалять целый кусок изнутри.

Жесть, если честно (что нету удаления куска). Ну и что значит, нет операции? Можно самому накатать, должно быть быстро.

kokoc88

Жесть, если честно (что нету удаления куска).

Нет, ну жести нет, есть subList(from, to) его можно очистить clear; поскольку всё это обёртки, то выполняется без копирования.

prehack

Я, наверно, приведу пример, когда LinkedList лучше ArrayList . Необходимо было плоский файл одного формата (ФИО, Сумма, Дата и т.д.) преобразовать в другой формат, при этом последовательность колонок менялась, какие-то колонки перемножались (т.е. добавлялись новые какие-то удалялись. Т.е как-раз было множество всяких перестановок по столбцам.
Соответсвенно получить в памяти структуру с необходимым форматом было легче и быстрее(по времени) используя LinkedList.
(Правда писалось на C#)

Оставить комментарий