Данные лежат в основе любого нетривиального приложения — и хотя Ruby предоставляет отличные классы Array и Hash с некоторой серьезной поддержкой синтаксиса, все остальное довольно редко встречается в стандартной библиотеке.
Когда вы выбираете структуру данных для своего проекта, выходящую за рамки стандартного Hash and Array, основным соображением и, действительно, основной мотивацией для переключения, часто является эффективность структуры данных. В этой статье я расскажу о том, как мы можем сравнивать структуры данных с точки зрения эффективности.
Мы будем использовать списки ссылок в качестве примера.
Краткий обзор массива
Для целей этой статьи, когда я говорю о массиве, я имею в виду реализацию массива в Ruby, которая несколько отличается от реализации многих языков программирования более низкого уровня. Во-первых, он не имеет ограничений ни по типу, ни по размеру данных, которые можно вставить. Во-вторых, это динамически изменяемый размер, что означает, что операции, которые увеличивали бы размер, больше не (или редко) требуют дорогого шага копирования массива в старшего брата.
Все примеры и тесты даны с использованием ruby 1.9.3, с наивно реализованным классом Array
Класс сложности?
Чтобы понять, почему вы предпочитаете одну структуру данных другой, полезно иметь возможность измерить и классифицировать их работу по мере роста их входных данных. Мы помещаем алгоритмы с аналогичной стоимостью в классы сложности, чтобы сравнить их. Некоторые алгоритмы занимают одинаковое количество времени для запуска независимо от входных данных, некоторые растут линейно с их входом, а некоторые растут, например, в геометрической прогрессии.
Когда мы говорим о «времени» запуска, редко сравниваются два алгоритма с использованием эталонных тестов, которые подвержены различиям в таких вещах, как язык программирования, скорость машины и активность сборщика мусора. Вместо этого ученые-компьютерщики будут смотреть на количество значимых действий, которые алгоритм должен выполнить, чтобы завершить.
Значимое действие скорее зависит от предметной области. Например, когда речь идет об алгоритмах сортировки, значимым действием может быть сравнение одного значения с другим.
Алгоритмы также имеют тенденцию иметь постоянную стоимость. То есть часть общей стоимости, которая не зависит от размера входных данных. Когда вы думаете о больших наборах данных, вы обычно игнорируете эту стоимость. Для любого нетривиального приложения с большим набором данных скорость роста будет быстро уменьшаться даже при самых больших постоянных затратах по мере роста входных данных.
Например, если алгоритм имеет постоянную стоимость ’10’ (скажем, в секундах), но требует ввода ^ 2 времени для запуска, то для ввода 2 константа может составлять значительную часть из 14 секунд, которые потребуются для выполнения. Но что, если ваш вклад скажет, скажем, 1 миллиард? Ну, вам нужно было бы начать процесс за некоторое время до большого взрыва. В этом контексте константа становится ничтожной.
Есть несколько очень удобных обозначений, которые мы можем использовать при сравнении алгоритмов. Большой O используется для выражения наихудшего сценария для данного алгоритма. Таким образом, мы могли бы сказать, что алгоритм x равен O (n), что означает, что в его худшем случае алгоритм x будет иметь время выполнения 15 значимых операций для входа 15. Однако если x имел время выполнения O (n * 15), мы бы посмотрели на 225 значимых операций.
Связанные списки
Связанные списки являются одной из самых простых структур данных, которые вы можете получить, наряду с традиционными массивами. В то время как массив представляет собой набор выделенных сегментов памяти с содержимым внутри них, связанный список представляет собой набор узлов, где каждый узел имеет указатель на следующий узел.
Подумайте о комоде из 10 ящиков. С массивом у вас есть каждый из этих ящиков с номерами от 0 до 9 с некоторым значением в каждом из розыгрышей. Чтобы найти элемент в ящике 2, просто откройте этот ящик и получите свой предмет.
Однако в связанном списке номера розыгрышей не имеют значения. Это могут быть случайные числа, цвета или изображения кошек. Все, что вы знаете с самого начала, это то, какой ящик является первым в списке. Чтобы найти второй предмет, вы должны открыть первый ящик и прочитать инструкцию, указывающую на местоположение следующего ящика в последовательности.
Если мы перебираем и массив, и связанный список от начала до конца, то потребуется O (n), чтобы пройти весь список. Для каждого элемента в списке мы должны открыть ровно один ящик.
Разница, однако, возникает, когда мы пытаемся найти элемент в списке i . В случае с массивом мы можем просто открыть ящик и покончить с ним — дать случайному доступу наихудший сценарий O (1). В связанном списке, однако, мы должны пройти через все ящики, пройдя по указателям и найдя наш элемент. Если элемент, который мы ищем, находится в конце списка, тогда мы должны сделать n открытий ящика, что дает сложность O (n).
Вы можете спросить, почему мы тогда использовали связанный список? Что ж, в случаях, когда нам нужно вставить элемент где-то в списке (и если мы уже знаем, в какой ящик находится элемент, который мы хотим вставить после того, как он находится), мы можем просто заменить указатель на следующий элемент в предыдущем ящике элементов на наш новый элемент в нашем новом ящике, а затем наш новый ящик указывает на элемент, который был ранее в этом положении. Это означает, что вставка займет не более одного открытого ящика, поэтому мы имеем сложность O (1).
Однако в случае массивов, если мы хотим поместить новый элемент в верхний ящик, мы должны переместить каждый элемент в каждом ящике ниже этого элемента на один. Это означает, что у нас будет открыто до n ящиков, что дает сложность O (n).
Давайте рассмотрим пример кода с простой реализацией связанного списка и некоторые тесты, чтобы увидеть, как это работает.
| class LinkedListNode | |
| attr_accessor :next, :value | |
| def initialize(value) | |
| @value = value | |
| end | |
| end | |
| class LinkedList | |
| attr_reader :last, :first | |
| def initialize(starting_values = []) | |
| starting_values.each{|a| add(a)} | |
| end | |
| def add(item) | |
| set_last_as LinkedListNode.new(item) | |
| end | |
| def add_at(index, what) | |
| add_after(at(index),what) | |
| end | |
| def add_after(item, what) | |
| what = LinkedListNode.new(what) | |
| what.next = item.next if item.next | |
| item.next = what | |
| end | |
| def at(index) | |
| i = 0 | |
| each{|a| return a if i == index; i +=1} | |
| end | |
| def each(&block) | |
| i = first | |
| while i | |
| yield i | |
| i = i.next | |
| end | |
| end | |
| def each_value(&block) | |
| each_in_box{|a| yield a.value} | |
| end | |
| protected | |
| def set_last_as(node) | |
| if first | |
| @last.next = node | |
| @last = node | |
| else | |
| @first = @last = node | |
| end | |
| end | |
| end | |
| require «benchmark» | |
| puts ‘Adding to the end’ | |
| puts ‘Array’ | |
| time = Benchmark.measure do | |
| a = Array.new() | |
| (0..10000).each do |i| | |
| a << i | |
| end | |
| end | |
| puts time | |
| puts ‘LinkedList’ | |
| time = Benchmark.measure do | |
| a = LinkedList.new() | |
| (0..10000).each do |i| | |
| a.add i | |
| end | |
| end | |
| puts time | |
| puts ‘Adding lots of items to a few indexes’ | |
| puts ‘Array’ | |
| a = (1..10000).to_a | |
| time = Benchmark.measure do | |
| 10.times do | |
| el = rand(1000) | |
| 10000.times do | |
| a.insert(el, «hello world») | |
| end | |
| end | |
| end | |
| puts time | |
| puts ‘LinkedList’ | |
| a = LinkedList.new((1..10000).to_a) | |
| time = Benchmark.measure do | |
| 10.times do | |
| el = a.at(rand(1000)) | |
| 10000.times do | |
| a.add_after(el, «hello world») | |
| end | |
| end | |
| end | |
| puts time | |
| #=> Output | |
| #Array | |
| # 0.000000 0.000000 0.000000 ( 0.003510) | |
| #LinkedList | |
| # 0.020000 0.000000 0.020000 ( 0.021374) | |
| #Adding lots of items to a few indexes | |
| #Array | |
| # 3.420000 0.020000 3.440000 ( 3.441180) | |
| #LinkedList | |
| # 0.260000 0.000000 0.260000 ( 0.263655) |
by В первом примере мы создаем наш список. Обе эти операции имеют сложность O (n). Вы заметите, что версия Array удобно превосходит связанный список. Это потому, что, как я упоминал ранее, мы сравниваем собственный класс Array 1.9.3 с чистой реализацией Ruby, которая имеет некоторые встроенные затраты производительности для каждой операции.
Во втором тесте мы выбираем 10 случайных элементов в списках и добавляем 10000 элементов после этой точки в каждую коллекцию. Этот пример действительно показывает силу связанных списков и то, как разница в их классах сложности для этой операции приводит к фактическим различиям в тестах.
Заворачивать
Надеемся, что эта статья дала вам разумное, хотя и краткое, представление о мире алгоритмов и сложности структуры данных, а также о том, как класс сложности влияет на производительность в реальном мире. Если вы хотите писать приложения, работающие с большими объемами данных, жизненно важно, вы решаете, какие операции с этими данными вы будете выполнять чаще всего, и выбираете структуру данных, которая хорошо выполняет эту операцию. Например, наш класс связанных списков был бы отличным кандидатом, если вы планируете много вставлять в середину списков, а не много произвольного доступа к этим спискам.
Если у вас есть какие-либо вопросы или я ошибаюсь, я буду болтаться в разделе комментариев.