Статьи

3 Методы сортировки задач в алгоритмах и классах структуры данных

Февраль 23, 2019

# 1: Сортировка огромных файлов

Сортировка больших файлов может быть не такой простой, как реализация алгоритма сортировки. Как только файл не помещается в память, должны быть применены более разумные реализации. Одним из способов является сортировка файла на жестком диске. Отметим, что не каждый алгоритм легко адаптируется для решения подобных задач. Итак, ваша задача в этом упражнении — решить, какие алогритмы хороши для решения проблемы и какой подход можно использовать для обработки больших файлов?

  1. Обсудите, какие операции эффективны при извлечении / обработке данных с жесткого диска
  2. Обсудите, какие операции нужны в разных алгоритмах
  3. Создайте таблицу для отображения результатов и выберите наиболее подходящий алгоритм.

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

Для этого вы можете отсортировать этот снимок всех ревизий википедии, взятых из немецкой википедии 2011 . Файл имеет несжатый размер 3,1 гигабайта и состоит из 128 миллионов строк. В частности, он уже содержит частичный порядок. 

# 2: Нахождение k наименьшего элемента в несортированном списке

Ваша задача — найти самый маленький элемент из несортированного списка. (спасибо Роберту Седжвику за вдохновение!)

Очевидно, что одним из подходов будет сортировка всех данных и затем получение k-го элемента. Время выполнения этого подхода будет равно O (n log (n)). Мы хотим добиться этого в линейной среде выполнения, что возможно благодаря помощи функции разделения быстрой сортировки.

После вызова функции разбиения неупорядоченный список разделяется на два подсписка с длинами i и ni. Первый список содержит первые элементы i (не обязательно отсортированные). сравнение i с k говорит вам погоду для поиска в первом или втором подсписке для элемента.

  • Используйте эту идею для реализации findMinK (массив ArrayList <Integer>, int k, int l, int r)
  • Протестируйте время выполнения вашей реализации с примитивным подходом первой сортировки. Для тестирования вы можете просто скачать рабочий код testframe ниже. В вашей функции вы должны увеличивать глобальную переменную cmpcnt каждый раз, когда функция разделения меняет элементы в списке
  • Запишите рекурсивное уравнение вашего решения и решите его, чтобы доказать, что среднее время выполнения также теоретически линейно.
  • Сравните это поведение во время выполнения с быстрой сортировкой (следующее упражнение) и объясните, почему эти подходы относятся к разным классам сложности.
  • import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;
 
public class mink {
	static public int cmpcnt = 0;
 
	public static void main(String[] args) {
		testFramework();
 
	}
 
	public static int findMinK(ArrayList<Integer> array, int k, int l, int r) {
		// Implement here
	}
 
	public static int findMinK(ArrayList<Integer> array, int k){
		Collections.sort(array);
		return array.get(k);
	}
 
	private static void testFramework() {
		ArrayList<Integer> a = new ArrayList<Integer>();
		for (int j=2;j<8;j++){
			a.clear();
			for (int i=0;i<(int)Math.pow(10, j);i++){
				a.add(i);
			}
			System.out.println("nn"+a.size()+" Elementsnn");
			double slow=0;
			double fast=0;
			for (int i = 0; i < 10; i++) {
				cmpcnt = 0;
				Collections.shuffle(a);
				int k = (int)(Math.random()*(Math.pow(10, j)-1))+1;
 
				System.out.println("test run number: " + i + " find: " + k);
 
				long start = System.currentTimeMillis();
				findMinK(a, k, 0, a.size()-1);
				long end = System.currentTimeMillis();
				long smarttime=(end-start);
				fast = fast + smarttime;
				System.out.println("SMART ALGO t --- time in ms: " + smarttime + " comparisons: "
						+ cmpcnt);
 
				start = System.currentTimeMillis();
				findMinK(a, k);
				end = System.currentTimeMillis();
				long slowtime = (end-start);
				System.out.println("WITH SORTING t --- time in ms: " + slowtime);
				System.out.println("sorting is " +(double)slowtime/(double)smarttime + " times slower");
				slow = slow + slowtime;
			}			
			System.out.println("sorting (="+slow+"ms) is " +slow/fast + " times slower than smart algo (="+fast+"ms)");
		}
	}	
}

№ 3: Решение рекурсивных уравнений: проверка времени выполнения быстрой сортировки

Быстрая сортировка — вероятностный алгоритм, и его рекурсивное уравнение задается неявным уравнением.

T (n) = n + 1 / n sum_ {i = 1} ^ n (T (i) + T (ni))


    Объясните значение суммы в этом уравнении и ее связь со стохастикой.

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

1 / n sum_ {i = 1} ^ n (T (i) + T (ni)) = 2 / n sum_ {i = 1} ^ n (T (i)) = 2 / n (T (n) + sum_ {I = 1} ^ {N-1} (Т (я)))

Если вам нравится этот пост, вам могут понравиться эти посты:

  1. Мой блог угадывает ваше имя — Бинарный поиск по классу Алгоритмы и структуры данных Бинарный поиск http://en.wikipedia.org/wiki/Binary_search_algorithm — очень простой алгоритм в компьютере …
  2. упражнение по сбалансированным бинарным деревьям поиска для алгоритмов и структур данных класса Я создал несколько упражнений, касающихся бинарных деревьев поиска. Этот раз…
  3. Как переместить каталог WordPress: Проблемы с загрузкой_path wp-content / uploads Недавно я был вынужден переместить сайт WordPress на …
  4. Структура данных для потоков социальных новостей в базах данных Graph ОБНОВЛЕНИЕ: посмотрите на http://www.rene-pickhardt.de/graphity для более научного обзора и …
  5. Об интернет-стартапах В сети уже появились действительно классные интернет-продукты …

 

37
Share: