Рубрика «list»

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

В этой статье:

  • формируем несколько базовых классов и интерфейсов для работы с RecyclerView и RecyclerView.Adapter
  • подключим одну библиотеку из Android Jetpack (по желанию, сначала без нее)
  • для еще более быстрой разработки — вариант темплейта в конце статьи ;)

Читать полностью »

В Python, есть два похожих типа — список (list) и кортеж (tuple). Самая известная разница между ними состоит в том, что кортежи неизменяемы.

Вы не можете изменить объекты в tuple:

>>> a = (1,2,3)
>>> a[0] = 10
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'tuple' object does not support item assignment

Но вы можете модифицировать изменяемые объекты внутри кортежа:

>>> b = (1,[1,2,3],3)
>>> b[1]
[1, 2, 3]
>>> b[1].append(4)
>>> b
(1, [1, 2, 3, 4], 3)

Читать полностью »

Приветствую вас!
После изучения коллекций, а именно такие реализации List, как ArrayList и LinkedList, возникла идея, а почему бы не объединить эти структуры данных в одну и посмотреть, что из этого получится.

Зачем это нужно?

  • Проблема ArrayList — у него есть начальный размер по умолчанию DEFAULT_CAPACITY или заданный размер initialCapacity, при превышении этого размера, создается новый массив большего размера, при этом туда копируются данные из старого массива, что по времени очень затратно и именно это дает в наихудшем случае алгоритмическую сложность O(n)
  • Проблема LinkedList — здесь наоборот, добавить новый элемент, это всего лишь добавить новую связь (создать еще одну Node и добавить ссылку на неё), но операция получения элемента по индексу очень затратна, т.к. нужно будет пройтись по всему списку от начала, что очень затратно и дает O(n)

Решение

Что если создать такую структуру данных, при которой вставка и получение любого элемента будет за константное время. Буду использовать технологию ArrayList без пересоздания массива, что конечно же проигрывает по памяти, но выигрывает в скорости, т.к. память дешевая и её очень много, выигрыш в производительности считаю приоритетным.
Для того чтобы связать их между собой, буду использовать двусвязный список:
Что будет если объединить ArrayList и LinkedList? - 1

Читать полностью »

Это седьмая статья из цикла «Теория категорий для программистов». Предыдущие статьи уже публиковались на Хабре:

Функторы

За понятием функтора стоит очень простая, но мощная идея (как бы заезжено это ни прозвучало). Просто теория категорий полна простых и мощных идей. Функтор есть отображение между категориями. Пусть даны две категории C и D, а функтор F отображает объекты из C в объекты из D — это функция над объектами. Если a — это объект из C, то будем обозначать его образ из D как F a (без скобок). Но ведь категория — это не только объекты, но еще и соединяющие их морфизмы. Функтор также отображает и морфизмы — это функция над морфизмами. Но морфизмы отображаются не как попало, а так, чтобы сохранять связи. А именно, если морфизм f из C связывает объект a с объектом b,

f :: a -> b

то образ f в D, F f, связывает образ a с образом b:

F f :: F a -> F b

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

Функторы (глава книги «Теория категорий для программистов») - 1Читать полностью »

1Учитывая тот факт, что на LinkedIn зарегистрировано более 380 миллионов человек, довольно трудно отделить мух от котлет. Представляю вам список из девяти человек, являющихся одними из самых активных и уважаемых пользователей LinkedIn в технологической отрасли.

LinkedIn по заказу CIO недавно прочесал базы своих пользователей, чтобы определить наиболее активных и влиятельных пользователей работающих в IT-индустрии. Так как из всей базы можно было бы составить список выходящий далеко за тысячу участников, его решили ограничить регулярностью постов, нативностью английского и согласием участника. Таким образом и был сформирован список. Вообще у всяких списков есть свои плюсы, хотя многие их не очень то жалуют. Мне, например, частенько везет и я нахожу в списках различных интересных персонажей, которых просто так не найти. Ну что же, приступим.
Читать полностью »

Приветствую Вас!

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

Не так давно я считал. что нет оправдания использованию java.util.LinkedList в качестве реализации java.util.List. Но что-то заставило меня его поискать. Давайте разберемся. Любой грамотный Java-специалист знает, что java.util.ArrayList нужно использовать тогда, когда нам нужен быстрый доступ по индексу, а java.util.LinkedList, если нам нужно вставлять или удалять элементы в середине списка. Не многие из них догадываются, что если мы будем вставлять или удалять элементы в середине списка методами remove(int index) и add(int index, E element), то на поиск нужного элемента будет затрачено время в среднем пропорциональное размеру списка O(N). Так когда же возникает выгода от использования java.util.LinkedList?
Читать полностью »

Мне было интересно, какие коллекции сколько съедают дополнительной памяти при хранении объектов. Я провёл замеры накладных расходов для популярных коллекций, предполагающих хранение однотипных элементов (то есть списки и множества) и свёл результаты на общий график. Вот картинка для 64-битной Hotspot JVM (Java 1.6):
Накладные расходы памяти у коллекций
Читать полностью »

Всем привет.

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

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

Одним из представителей этой группы является Unrolled linked list.

Что же это такое?
Читать полностью »

Односвзязный список — это фундаментальная структура данных, о которой все знают и повсеместно используют. Все знают почему и в каких случаях он эффективнее вектора, какие операции имеют линейную сложность, а какие — константную…

Хотя постойте, знаете ли вы какова соложность функции size ()?
«Конечно же я знаю — О(1)!», ответят многие из вас, «Что может быть проще?»

size_type  size() const                             
{
       return _size;
}

Тривиально, эффективно и безопасно, не так ли?
Я бы реализовал эту функцию именно так, большинство из вас сделали бы тоже самое.

Однако, те, кто писал реализацию GNU STL, другого мнения на этот счет.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js