Кощей Роман

Appearance

Лабораторна робота №1 ​

Умова ​

Написати програму мовою C# з можливістю вибору різних алгоритмів пошуку. Продемонструвати роботу ефективність (час виконання) програм на різних структурах даних (масив, лінійний зв’язаний список), з різними умовами, що забезпечують зменшення часу виконання. Навести аналіз отриманих результатів.

Реалізувати алгоритми:

  • пошуку перебором елемента масиву, що дорівнює заданому значенню.
  • пошуку з бар'єром елемента масиву, що дорівнює заданому значенню.
  • бінарного пошуку елемента масиву рівного заданому значенню.
  • бінарного пошуку елемента масиву, рівного заданому значенню, в якій нове значення індексу m визначалося б не як середнє значення між L і R, а згідно з правилом золотого перерізу.

Аналіз ​

Хоч можна звести пошук для масиву та для зв'язного списку під один інтерфейс IEnumerable, але це не найкраще рішення в даній ситуації. Тож ми створимо кожну функцію для кожної структури даних.

Я віддаю переважання розширенням для створення функцій, що працюють над вже вбудованими типами.

Будуть проблеми зі зв'язним списком при бінарних пошуках. Бо зв'язний список не має індексації, а лише зв'язки.

Структура основних вхідних та вихідних даних ​

Кожна функція сортування буде приймати массив/список й число яке ми шукаємо. А повертати буде індекс. Якщо число не знайдено в масиві то повертаємо -1.

Алгоритм розв'язання задачі ​

По першу подивимося в інтернеті реалізації для вказаних алгоритмів сортировки та спитаємо ChatGPT.

Зрозуміємо, що те, що дав ChatGPT, доволі сумнівне та треба переписати самостійно. Проблем з реалізацією для масивів немає, бо є в інтернеті як це працює.

А ось для зв'язних списків треба самостійно переписати те, що написали для масиву.

Текст програми ​

Program.cs

cs
using Lab1;
using System.Diagnostics;

int[] array = GenerateArray(1000000);
var linkedList = new LinkedList<int>(array);

var search = array[new Random().Next(0, array.Length - 1)];

MeasureSearchTime("Traversing search for array", () => array.TraversingSearch(search));
MeasureSearchTime("Traversing search for linked list", () => linkedList.TraversingSearch(search));

MeasureSearchTime("Barrier search for array", () => array.BarrierSearch(search));
MeasureSearchTime("Barrier search for linked list", () => linkedList.BarrierSearch(search));

Array.Sort(array);
linkedList = SortLinkedList(linkedList);

MeasureSearchTime("Binary search for array", () => array.BinarySearch(search));
MeasureSearchTime("Binary search for linked list", () => linkedList.BinarySearch(search));

MeasureSearchTime("Golden Ratio Binary search for array", () => array.GoldenRatioBinarySearch(search));
MeasureSearchTime("Golden Ratio Binary search for linked list", () => linkedList.GoldenRatioBinarySearch(search));

static int[] GenerateArray(int count)
{
    int[] arr = new int[count];
    for (int i = 0; i < count; i++)
    {
        arr[i] = new Random().Next();
    }
    return arr;
}

static void MeasureSearchTime(string message, Func<int> search)
{
    Stopwatch stopwatch = new();
    stopwatch.Start();
    var index = search();
    stopwatch.Stop();

    Console.ForegroundColor = ConsoleColor.Yellow;
    Console.WriteLine($"{message}: index={index} time={stopwatch.ElapsedTicks} ticks");
    Console.ForegroundColor = ConsoleColor.White;
}

static void PrintEnumerable(IEnumerable<int> nums)
{
    foreach (var num in nums)
    {
        Console.Write(num);
        Console.Write(" ");
    }
    Console.WriteLine();
}

static LinkedList<int> SortLinkedList(LinkedList<int> linkedList)
{
    int[] array = new int[linkedList.Count];
    linkedList.CopyTo(array, 0);

    Array.Sort(array);

    return new LinkedList<int>(array);
}
using Lab1;
using System.Diagnostics;

int[] array = GenerateArray(1000000);
var linkedList = new LinkedList<int>(array);

var search = array[new Random().Next(0, array.Length - 1)];

MeasureSearchTime("Traversing search for array", () => array.TraversingSearch(search));
MeasureSearchTime("Traversing search for linked list", () => linkedList.TraversingSearch(search));

MeasureSearchTime("Barrier search for array", () => array.BarrierSearch(search));
MeasureSearchTime("Barrier search for linked list", () => linkedList.BarrierSearch(search));

Array.Sort(array);
linkedList = SortLinkedList(linkedList);

MeasureSearchTime("Binary search for array", () => array.BinarySearch(search));
MeasureSearchTime("Binary search for linked list", () => linkedList.BinarySearch(search));

MeasureSearchTime("Golden Ratio Binary search for array", () => array.GoldenRatioBinarySearch(search));
MeasureSearchTime("Golden Ratio Binary search for linked list", () => linkedList.GoldenRatioBinarySearch(search));

static int[] GenerateArray(int count)
{
    int[] arr = new int[count];
    for (int i = 0; i < count; i++)
    {
        arr[i] = new Random().Next();
    }
    return arr;
}

static void MeasureSearchTime(string message, Func<int> search)
{
    Stopwatch stopwatch = new();
    stopwatch.Start();
    var index = search();
    stopwatch.Stop();

    Console.ForegroundColor = ConsoleColor.Yellow;
    Console.WriteLine($"{message}: index={index} time={stopwatch.ElapsedTicks} ticks");
    Console.ForegroundColor = ConsoleColor.White;
}

static void PrintEnumerable(IEnumerable<int> nums)
{
    foreach (var num in nums)
    {
        Console.Write(num);
        Console.Write(" ");
    }
    Console.WriteLine();
}

static LinkedList<int> SortLinkedList(LinkedList<int> linkedList)
{
    int[] array = new int[linkedList.Count];
    linkedList.CopyTo(array, 0);

    Array.Sort(array);

    return new LinkedList<int>(array);
}

ArraySearch.cs

cs
namespace Lab1;

public static class ArraySearch
{
    public static int TraversingSearch(this int[] arr, int searchValue)
    {
        for (int i = 0; i < arr.Length; i += 1)
        {
            if (arr[i] == searchValue) { return i; }
        }
        return -1;
    }

    public static int BarrierSearch(this int[] nums, int searchValue)
    {
        if (nums.Length == 0) return -1;

        var lastIndex = nums.Length - 1;
        var last = nums[lastIndex];
        if (last == searchValue) return lastIndex;

        nums[lastIndex] = searchValue;

        int i = 0;
        while (nums[i] != searchValue)
        {
            i += 1;
        }

        nums[lastIndex] = last;
        return i < lastIndex ? i : -1;
    }

    public static int BinarySearch(this int[] nums, int searchValue)
    {
        int left = 0;
        int right = nums.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            if (nums[mid] == searchValue)
            {
                return mid; // Знайдено елемент, повертаємо індекс
            }
            else if (nums[mid] < searchValue)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }

        return -1; // Елемент не знайдено
    }

    private const double goldenRatio = 1.618033988749895;

    public static int GoldenRatioBinarySearch(this int[] arr, int searchValue)
    {
        int left = 0;
        int right = arr.Length - 1;

        while (left <= right)
        {
            int m = (int)(right - (right - left) / goldenRatio);
            int midValue = arr[m];

            if (midValue == searchValue)
            {
                return m;
            }
            else if (midValue < searchValue)
            {
                left = m + 1;
            }
            else
            {
                right = m - 1;
            }
        }

        return -1;
    }
}
namespace Lab1;

public static class ArraySearch
{
    public static int TraversingSearch(this int[] arr, int searchValue)
    {
        for (int i = 0; i < arr.Length; i += 1)
        {
            if (arr[i] == searchValue) { return i; }
        }
        return -1;
    }

    public static int BarrierSearch(this int[] nums, int searchValue)
    {
        if (nums.Length == 0) return -1;

        var lastIndex = nums.Length - 1;
        var last = nums[lastIndex];
        if (last == searchValue) return lastIndex;

        nums[lastIndex] = searchValue;

        int i = 0;
        while (nums[i] != searchValue)
        {
            i += 1;
        }

        nums[lastIndex] = last;
        return i < lastIndex ? i : -1;
    }

    public static int BinarySearch(this int[] nums, int searchValue)
    {
        int left = 0;
        int right = nums.Length - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            if (nums[mid] == searchValue)
            {
                return mid; // Знайдено елемент, повертаємо індекс
            }
            else if (nums[mid] < searchValue)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }

        return -1; // Елемент не знайдено
    }

    private const double goldenRatio = 1.618033988749895;

    public static int GoldenRatioBinarySearch(this int[] arr, int searchValue)
    {
        int left = 0;
        int right = arr.Length - 1;

        while (left <= right)
        {
            int m = (int)(right - (right - left) / goldenRatio);
            int midValue = arr[m];

            if (midValue == searchValue)
            {
                return m;
            }
            else if (midValue < searchValue)
            {
                left = m + 1;
            }
            else
            {
                right = m - 1;
            }
        }

        return -1;
    }
}

LinkedListSearch.cs

cs
namespace Lab1;

public static class LinkedListSearch
{
    public static int TraversingSearch(this LinkedList<int> list, int searchValue)
    {
        int index = -1;
        foreach (var num in list)
        {
            index += 1;
            if (num == searchValue) return index;
        }
        return -1;
    }

    public static int BarrierSearch(this LinkedList<int> nums, int searchValue)
    {
        if (nums.Count == 0) return -1;

        var last = nums.Last;
        var lastValue = last!.Value;
        if (lastValue == searchValue) return nums.Count - 1;

        last.Value = searchValue;
        int i = 0;
        var current = nums.First;
        while (current!.Value != searchValue)
        {
            current = current.Next;
            i += 1;
        }

        last.Value = lastValue;
        return i < nums.Count - 1 ? i : -1;
    }

    public static int BinarySearch(this LinkedList<int> sortedList, int searchValue)
    {
        int index = 0;

        int left = 0;
        int right = sortedList.Count - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            LinkedListNode<int>? currentNode = MoveToIndex(sortedList, mid);

            if (currentNode.Value == searchValue)
            {
                return index + mid;
            }
            else if (currentNode.Value < searchValue)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }

        return -1;
    }

    public static int GoldenRatioBinarySearch(this LinkedList<int> linkedList, int searchValue)
    {
        int left = 0;
        int right = linkedList.Count - 1;

        const double goldenRatio = 1.618033988749895;

        while (left <= right)
        {
            int m = (int)(right - (right - left) / goldenRatio);
            LinkedListNode<int> midNode = MoveToIndex(linkedList, m);
            int midValue = midNode.Value;

            if (midValue == searchValue)
            {
                return m;
            }
            else if (midValue < searchValue)
            {
                left = m + 1;
            }
            else
            {
                right = m - 1;
            }
        }

        return -1;
    }

    private static LinkedListNode<T> MoveToIndex<T>(LinkedList<T> list, int index)
    {
        var currentNode = list.First;

        for (int i = 0; i < index; i++)
        {
            currentNode = currentNode.Next;
        }

        return currentNode;
    }
}
namespace Lab1;

public static class LinkedListSearch
{
    public static int TraversingSearch(this LinkedList<int> list, int searchValue)
    {
        int index = -1;
        foreach (var num in list)
        {
            index += 1;
            if (num == searchValue) return index;
        }
        return -1;
    }

    public static int BarrierSearch(this LinkedList<int> nums, int searchValue)
    {
        if (nums.Count == 0) return -1;

        var last = nums.Last;
        var lastValue = last!.Value;
        if (lastValue == searchValue) return nums.Count - 1;

        last.Value = searchValue;
        int i = 0;
        var current = nums.First;
        while (current!.Value != searchValue)
        {
            current = current.Next;
            i += 1;
        }

        last.Value = lastValue;
        return i < nums.Count - 1 ? i : -1;
    }

    public static int BinarySearch(this LinkedList<int> sortedList, int searchValue)
    {
        int index = 0;

        int left = 0;
        int right = sortedList.Count - 1;

        while (left <= right)
        {
            int mid = left + (right - left) / 2;

            LinkedListNode<int>? currentNode = MoveToIndex(sortedList, mid);

            if (currentNode.Value == searchValue)
            {
                return index + mid;
            }
            else if (currentNode.Value < searchValue)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }

        return -1;
    }

    public static int GoldenRatioBinarySearch(this LinkedList<int> linkedList, int searchValue)
    {
        int left = 0;
        int right = linkedList.Count - 1;

        const double goldenRatio = 1.618033988749895;

        while (left <= right)
        {
            int m = (int)(right - (right - left) / goldenRatio);
            LinkedListNode<int> midNode = MoveToIndex(linkedList, m);
            int midValue = midNode.Value;

            if (midValue == searchValue)
            {
                return m;
            }
            else if (midValue < searchValue)
            {
                left = m + 1;
            }
            else
            {
                right = m - 1;
            }
        }

        return -1;
    }

    private static LinkedListNode<T> MoveToIndex<T>(LinkedList<T> list, int index)
    {
        var currentNode = list.First;

        for (int i = 0; i < index; i++)
        {
            currentNode = currentNode.Next;
        }

        return currentNode;
    }
}

Набір тестів ​

Тести знаходяться в Program.cs. Кожним пошуком виконуємо пошук в масимі та зв'язному списку. Та заміряємо кількість часу, що вони займають.

cs
MeasureSearchTime("Traversing search for array", () => array.TraversingSearch(search));
MeasureSearchTime("Traversing search for linked list", () => linkedList.TraversingSearch(search));

MeasureSearchTime("Barrier search for array", () => array.BarrierSearch(search));
MeasureSearchTime("Barrier search for linked list", () => linkedList.BarrierSearch(search));

Array.Sort(array);
linkedList = SortLinkedList(linkedList);

MeasureSearchTime("Binary search for array", () => array.BinarySearch(search));
MeasureSearchTime("Binary search for linked list", () => linkedList.BinarySearch(search));

MeasureSearchTime("Golden Ratio Binary search for array", () => array.GoldenRatioBinarySearch(search));
MeasureSearchTime("Golden Ratio Binary search for linked list", () => linkedList.GoldenRatioBinarySearch(search));
MeasureSearchTime("Traversing search for array", () => array.TraversingSearch(search));
MeasureSearchTime("Traversing search for linked list", () => linkedList.TraversingSearch(search));

MeasureSearchTime("Barrier search for array", () => array.BarrierSearch(search));
MeasureSearchTime("Barrier search for linked list", () => linkedList.BarrierSearch(search));

Array.Sort(array);
linkedList = SortLinkedList(linkedList);

MeasureSearchTime("Binary search for array", () => array.BinarySearch(search));
MeasureSearchTime("Binary search for linked list", () => linkedList.BinarySearch(search));

MeasureSearchTime("Golden Ratio Binary search for array", () => array.GoldenRatioBinarySearch(search));
MeasureSearchTime("Golden Ratio Binary search for linked list", () => linkedList.GoldenRatioBinarySearch(search));

Результати тестування програми та аналіз отриманих помилок ​

Також після розігріву рантайму можна зауважити, що при невеликих обсягах даних зв'язний список має майже однакову швидкість, іноді навіть перевищуючи масив у пошуку з бар'єром.

Це трошки дивно. І, здається, ніби магія, але це C#.

Можливо, це пов'язано із тим, як ми формуємо зв'язний список. У моїх тестах він створюється на основі масиву, тому зв'язний список розташовує елементи поруч один з одним.

Для навіть більшої оптимізації ми можемо алакувати масив на стеку.