• Home
  • Syllabus
  • Schedule
  • Slides
  • All-Hands

On this page

  • Introduction
    • Motivation
  • Queue Implementations Analysis
    • Queue Structure and FIFO Principle
    • Implementations Overview
    • Key Operations
      • Key Implementation Examples
    • Implementation Considerations
      • SLL Queue Considerations
      • DLL Queue Considerations
      • Array-based Queue Considerations
      • Benchmarking
    • Running and Using the Tool
      • Setting Up
      • Running the Experiments
    • Output Analysis
      • Anton Hedlund
      • Anupraj Guragain
      • Joseph Oforkansi

What is the performance difference, measured in time when running a doubling experiment between a SLL queue, a DLL queue and a queue built with an array based list when performing basic operations?

post
queues
linked lists
doubling experiment
Authors

Javier Bejarano Jimenez

Finley Banas

Joseph Oforkansi

Anupraj Guragain

Anton Hedlund

Published

March 28, 2025

Introduction

Data structures play a critical role in efficient software development, influencing performance, scalability, and system responsiveness. Among them, queues are fundamental, powering applications such as task scheduling, messaging systems, and real-time data processing. In this project, our team explored three key queue implementations—Singly Linked List (SLL), Doubly Linked List (DLL), and Array-based Queue. This project seeks to answer our research question: What are the performance differences between SLL queue, DLL queue, and array-based queue implementations when executing basic operations (addfirst, addlast, removefirst, removelast, add (+), and iadd (+=)?. We analyzed their performance through benchmarking experiments using SystemSense.

As algorithm engineers tackling this project we considered multiple aspects, including:

Algorithmic Complexity: Understanding the time and space complexity of queue operations to determine trade-offs between different implementations.

Memory Management: Evaluating how memory allocation and deallocation affect performance, particularly in linked list-based vs. array-based implementations.

Concurrency Considerations: Investigating how these data structures behave in multi-threaded environments where multiple processes access and modify queues simultaneously.

Use Case Optimization: Identifying practical applications where each queue implementation excels, such as high-throughput systems, real-time event processing, and low-latency applications.

Benchmarking Methodology: Designing experiments to measure execution times, analyze scaling behavior, and compare performance under different workloads.

Through this project, we aim to provide insights into the efficiency of these queue implementations and guide the selection of an optimal data structure based on application requirements. By profiling and analyzing queue operations, we not only enhance our understanding of core data structures but also develop practical skills in performance analysis, a crucial skill in algorithm engineering and systems design.

Motivation

Efficient data structures are essential in software development, especially when dealing with queues in real-world applications such as scheduling systems, task management, and networking. Different queue implementations like Singly Linked List (SLL), Doubly Linked List (DLL), and Array-based Queue offer trade-offs in terms of performance. Our project aims to benchmark these tradeoffs and analyze the data by comparing the execution times of the queue operations.

Queue Implementations Analysis

Queue Structure and FIFO Principle

Queues follow the First-In-First-Out (FIFO) principle where elements are added at the rear and removed from the front, ensuring sequential processing order.

Implementations Overview

This project explores three queue implementations:

  1. Singly Linked List (SLL) Queue
    • Uses one-directional nodes with next references
    • Maintains both head and tail pointers for efficient operations
    • Each node stores only the value and next reference
  2. Doubly Linked List (DLL) Queue
    • Uses bidirectional nodes with both prev and next references
    • Maintains both head and tail pointers
    • Each node stores value, previous, and next references
  3. Array-based Queue
    • No explicit node structure, just a container of elements
    • Optimized for operations at both ends

Key Operations

All implementations support these core operations: - enqueue: Add element to the rear (O(1) in all implementations) - dequeue: Remove element from the front (O(1) in all implementations) - peek: View front element without removing (O(1) in all implementations) - __add__: Concatenate queues (O(1) in linked lists, O(n) in array-based) - __iadd__: In-place concatenation (O(1) in linked lists, O(n) in array-based)

Key Implementation Examples

Enqueue Operation (SLL)

def enqueue(self, value: Any) -> None:
    """Add an element to the end of the queue. O(1) operation using tail pointer."""
    new_node = Node(value)
    if self.is_empty():
        self.head = new_node
    else:
        self.tail.next = new_node  # Directly append at tail
    self.tail = new_node  # Update tail pointer
    self.size += 1

Dequeue Operation (DLL)

def dequeue(self) -> Any:
    """Remove and return the first element from the queue. O(1) operation."""
    if self.is_empty():
        raise IndexError("Queue is empty")
    value = self.head.value
    self.head = self.head.next
    if self.head is None:
        self.tail = None
    else:
        self.head.prev = None
    self.size -= 1
    return value

Queue Concatenation (Array-based)

def __add__(self, other: "ListQueueDisplay") -> "ListQueueDisplay":
    """Concatenate two queues. O(n) operation."""
    result = ListQueueDisplay()
    result.items = deque(self.items)  # Copy first queue
    result.items.extend(other.items)  # Append second queue
    return result

Implementation Considerations

SLL Queue Considerations

  • Simpler structure with less memory overhead per node
  • Forward-only traversal limits some operations
  • Efficient concatenation due to tail pointer

DLL Queue Considerations

  • Bidirectional links enable more flexible operations
  • Higher memory usage due to extra pointer per node
  • Supports easy traversal in both directions

Array-based Queue Considerations

  • No manual pointer management needed
  • Leverages efficient implementation of Python’s deque
  • Internal array may require occasional reallocation

Benchmarking

There are two main benchmarking function in our project.

Basic analysis

def analyze_queue(queue_class, size=1000):
    """Analyze a queue implementation."""
    approach = next(
        (k for k, v in QUEUE_IMPLEMENTATIONS.items() if v == queue_class), None
    )
    if approach is None:
        console.print("[red]Unknown queue implementation[/red]")
        return

    console.print(f"\n{approach.value.upper()} Queue Implementation")

    try:
        queue = queue_class()
        operations = []

        # Test enqueue
        enqueue_time = time_operation(lambda: [queue.enqueue(i) for i in range(size)])
        operations.append(("enqueue", enqueue_time, size))

        # Test dequeue
        dequeue_count = size // 2
        dequeue_time = time_operation(
            lambda: [queue.dequeue() for _ in range(dequeue_count)]
        )
        operations.append(("dequeue", dequeue_time, dequeue_count))

        # Refill queue
        for i in range(dequeue_count):
            queue.enqueue(i)

        # Test peek
        peek_count = size // 3
        peek_time = time_operation(lambda: [queue.peek() for _ in range(peek_count)])
        operations.append(("peek", peek_time, peek_count))

        # Test concat
        other = queue_class()
        for i in range(size // 10):
            other.enqueue(i)
        concat_time = time_operation(lambda: queue + other)
        operations.append(("concat", concat_time, size // 10))

        # Test iconcat
        iconcat_time = time_operation(lambda: queue.__iadd__(other))
        operations.append(("iconcat", iconcat_time, size // 10))

        # Display results in table
        table = Table(
            title=f"{approach.value.upper()} Queue Performance Analysis",
            box=box.ROUNDED,
            show_header=True,
            header_style="bold magenta",
        )
        table.add_column("Operation", style="cyan")
        table.add_column("Time (ms)", justify="right")
        table.add_column("Elements", justify="right")
        table.add_column("Time/Element (ms)", justify="right")

        for operation, time_taken, elements in operations:
            time_per_element = time_taken / elements if elements > 0 else 0
            table.add_row(
                operation,
                f"{time_taken * 1000:.6f}",  # Convert to milliseconds
                f"{elements:,}",
                f"{time_per_element * 1000:.6f}",  # Convert to milliseconds
            )

        console.print(Panel(table))

    except Exception as e:
        console.print(f"[red]Error testing {approach.value}: {str(e)}[/red]")
        import traceback

        console.print(traceback.format_exc())

This function performs a basic performance analysis with the following operations: - Enqueue: Adds size elements to the queue - Dequeue: Removes size/2 elements - Peek: Looks at size/3 elements without removing them - Concat: Concatenates with another queue of size size/10 - Iconcat: In-place concatenation with another queue of size size/10

Doubling experiment


def doubling(
    initial_size: int = typer.Option(100, help="Initial size for doubling experiment"),
    max_size: int = typer.Option(1000, help="Maximum size for doubling experiment"),
    dll: bool = typer.Option(True, help="Test DLL implementation"),
    sll: bool = typer.Option(True, help="Test SLL implementation"),
    array: bool = typer.Option(True, help="Test Array implementation"),
):
    """Run doubling experiment on queue implementations."""
    # Create results directory if it doesn't exist
    results_dir = Path("results")
    results_dir.mkdir(exist_ok=True)

    sizes = []
    current_size = initial_size
    while current_size <= max_size:
        sizes.append(current_size)
        current_size *= 2

    # Dictionary to store all results for plotting
    all_results = {}

    for approach, queue_class in QUEUE_IMPLEMENTATIONS.items():
        if not (
            (approach == QueueApproach.dll and dll)
            or (approach == QueueApproach.sll and sll)
            or (approach == QueueApproach.array and array)
        ):
            continue

        try:
            console.print(f"\n{approach.value.upper()} Queue Implementation")
            results = {
                "enqueue": [],
                "dequeue": [],
                "peek": [],
                "concat": [],
                "iconcat": [],
            }

            for size in sizes:
                queue = queue_class()

                # Enqueue
                enqueue_time = time_operation(
                    lambda: [queue.enqueue(i) for i in range(size)]
                )
                results["enqueue"].append(enqueue_time)

                # Dequeue
                dequeue_time = time_operation(
                    lambda: [queue.dequeue() for _ in range(size // 2)]
                )
                results["dequeue"].append(dequeue_time)

                # Refill queue
                for i in range(size // 2):
                    queue.enqueue(i)

                # Peek
                peek_time = time_operation(
                    lambda: [queue.peek() for _ in range(size // 3)]
                )
                results["peek"].append(peek_time)

                # Concat
                other = queue_class()
                for i in range(size // 10):
                    other.enqueue(i)

                concat_time = time_operation(lambda: queue + other)
                results["concat"].append(concat_time)

                # Iconcat
                iconcat_time = time_operation(lambda: queue.__iadd__(other))
                results["iconcat"].append(iconcat_time)

            # Store results for plotting
            all_results[approach.value] = results

            # Display results in table
            table = Table(
                title=f"{approach.value.upper()} Queue Doubling Experiment Results",
                box=box.ROUNDED,
                show_header=True,
                header_style="bold magenta",
            )
            table.add_column("Size (n)", justify="right")
            for operation in results.keys():
                table.add_column(operation, justify="right")

            for i, size in enumerate(sizes):
                row = [f"{size:,}"]
                for operation in results.keys():
                    value = results[operation][i]
                    if np.isnan(value):  # Check for NaN
                        row.append("N/A")
                    else:
                        row.append(f"{value * 1000:.6f}")  # Convert to milliseconds
                table.add_row(*row)

            console.print(Panel(table))

        except Exception as e:
            console.print(f"[red]Error testing {approach.value}: {str(e)}[/red]")
            import traceback

            console.print(traceback.format_exc())

    # Generate and save plots
    plot_results(sizes, all_results, results_dir)
    console.print(f"[green]Plots saved to [bold]{results_dir}[/bold] directory[/green]")

This doubling experiment does the following - Starts with initial_size and doubles the size until reaching max_size - For each size, measures the same operations as the basic analysis - Generates plots to visualize the results

Key benchmarking feature

Timing Mechanism

def time_operation(func):
    """Time an operation using high-precision counter."""
    try:
        # Warm up
        func()

        # Actual timing
        start_time = perf_counter()
        func()
        elapsed = perf_counter() - start_time
        return elapsed
    except Exception as e:
        console.print(f"[red]Error during operation: {str(e)}[/red]")
        return float("nan")
  • Uses perf_counter() for high-precision timing
  • Includes a warm-up run to avoid cold-start penalties
  • Returns elapsed time in seconds
Result Visualization
def plot_results(sizes, all_results, results_dir):
    """Generate and save plots for doubling experiment results."""
    operations = ["enqueue", "dequeue", "peek", "concat", "iconcat"]

    # Create log-log plots for each operation (keeping only these, removing regular operation plots)
    for operation in operations:
        # Skip regular plots for operations - only create log-log plots
        if len(sizes) > 2:  # Only create log plots if we have enough data points
            plt.figure(figsize=(10, 6))

            for impl, results in all_results.items():
                times = np.array(results[operation]) * 1000  # Convert to milliseconds
                if np.all(times > 0):  # Avoid log(0)
                    plt.loglog(
                        sizes, times, marker="o", label=f"{impl.upper()}", linewidth=2
                    )

            # Add reference lines for O(1), O(n), O(n²)
            x_range = np.array(sizes)
            # Add O(1) reference
            plt.loglog(
                x_range, np.ones_like(x_range) * times[0], "--", label="O(1)", alpha=0.5
            )
            # Add O(n) reference - scale to fit
            plt.loglog(
                x_range,
                x_range * (times[0] / x_range[0]),
                "--",
                label="O(n)",
                alpha=0.5,
            )
            # Add O(n²) reference - scale to fit
            plt.loglog(
                x_range,
                np.power(x_range, 2) * (times[0] / np.power(x_range[0], 2)),
                "--",
                label="O(n²)",
                alpha=0.5,
            )

            plt.title(
                f"Log-Log Plot for {operation.capitalize()} Operation", fontsize=16
            )
            plt.xlabel("Log Queue Size", fontsize=14)
            plt.ylabel("Log Time (ms)", fontsize=14)
            plt.grid(True, which="both", linestyle="--", alpha=0.5)
            plt.legend(fontsize=12)
            plt.tight_layout()

            # Save log-log plot
            log_plot_path = results_dir / f"{operation}_loglog_plot.png"
            plt.savefig(log_plot_path)
            plt.close()

    # Create regular performance plots for each implementation (keeping these, removing log-scale implementation plots)
    for impl, results in all_results.items():
        plt.figure(figsize=(10, 6))

        for operation in operations:
            times = np.array(results[operation]) * 1000  # Convert to milliseconds
            plt.plot(sizes, times, marker="o", label=operation, linewidth=2)

        plt.title(f"{impl.upper()} Queue Implementation Performance", fontsize=16)
        plt.xlabel("Queue Size (n)", fontsize=14)
        plt.ylabel("Time (ms)", fontsize=14)
        plt.grid(True, linestyle="--", alpha=0.7)
        plt.legend(fontsize=12)
        plt.tight_layout()

        # Save plot
        plot_path = results_dir / f"{impl}_performance.png"
        plt.savefig(plot_path)
        plt.close()
  • Creates log-log plots for each operation to show algorithmic complexity
  • Generates regular performance plots for each implementation
  • Saves all plots to a results directory
Error Handling
  • Gracefully handles exceptions during benchmarking
  • Report errors with detailed tracebacks
  • Continues testing other implementations if one fails
Output Format:
  • Uses Rich library for formatted console output
  • Displays results in tables with:
    • Operation name
    • Time taken (in milliseconds)
    • Number of elements
    • Time per element

References

  • AI agent of Cursor AI (Claude sonnet 3.7) was heavily used for the information, generation, debugging and implementaion of various code specifically main.py
  • https://algorithmology.org/
  • https://algorithmology.org/schedule/weekseven/
  • https://www.geeksforgeeks.org/queue-in-python/
  • https://stackoverflow.com/questions/45688871/implementing-an-efficient-queue-in-python
  • Chatgpt for information
  • Deepseek for information
  • Qwen for information

Running and Using the Tool

The benchmarking supports three queue implementations: - DLL (Doubly Linked List) - SLL (Singly Linked List) - Array-based Queue

Setting Up

To run the benchmarking tool, ensure you have Poetry installed onto your device. Navigate to the project directory and install dependencies if you have not already:

cd analyze && poetry install

Running the Experiments

The tool provides two main benchmarking experiments which can also be access by

poetry run analyze --help

Doubling Experiment

To run the doubling experiment, execute:

poetry run analyze doubling

This experiment measures how performance will scale with the increasing input sizes.

You can also run: poetry run analyze doubling --help for more details and detailed apporach

Implementation Performance Analysis

To analyze the performance of individual queue operations, run:

poetry run analyze analyze

This command will provide execution times for operations like peek, dequeue, and enqueue to compare their efficiency.

You can also run: poetry run analyze analyze --help for more details and detailed apporach

Output Analysis

Anton Hedlund

Run of systemsense

poetry run systemsense completeinfo
Displaying System Information

╭─────────────────────────────────────────────────────── System Information ───────────────────────────────────────────────────────╮
│ ╭──────────────────┬───────────────────────────────────────────────────────────────────────────────────────────────────────────╮ │
│ │ System Parameter │ Parameter Value                                                                                           │ │
│ ├──────────────────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────┤ │
│ │ battery          │ 79.00% battery life remaining, 6:15:00 seconds remaining                                                  │ │
│ │ cpu              │ arm                                                                                                       │ │
│ │ cpucores         │ 11 cores                                                                                                  │ │
│ │ cpufrequencies   │ Min: Unknown Mhz, Max: Unknown Mhz                                                                        │ │
│ │ datetime         │ 2025-03-26 22:32:34.509801                                                                                │ │
│ │ disk             │ Using 10.39 GB of 460.43 GB                                                                               │ │
│ │ hostname         │ MacBook-Pro-Anton.local                                                                                   │ │
│ │ memory           │ Using 6.58 GB of 18.00 GB                                                                                 │ │
│ │ platform         │ macOS-15.3.2-arm64-arm-64bit                                                                              │ │
│ │ pythonversion    │ 3.12.8                                                                                                    │ │
│ │ runningprocesses │ 594 running processes                                                                                     │ │
│ │ swap             │ Using 0.49 GB of 2.00 GB                                                                                  │ │
│ │ system           │ Darwin                                                                                                    │ │
│ │ systemload       │ Average Load: 2.82, CPU Utilization: 20.50%                                                               │ │
│ │ virtualenv       │ /Users/antonhedlund/Compsci/algorhytms_202/computer-science-202-algorithm-engineering-project-1-ahedlund… │ │
│ ╰──────────────────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────╯ │
╰──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

Displaying Benchmark Results

╭────────────────────────────────────────────────────────────────────────── Benchmark Results ──────────────────────────────────────────────────────────────────────────╮
│ ╭────────────────┬─────────────────────────────────────────────────────────────────╮                                                                                  │
│ │ Benchmark Name │ Benchmark Results (sec)                                         │                                                                                  │
│ ├────────────────┼─────────────────────────────────────────────────────────────────┤                                                                                  │
│ │ addition       │ [0.37942662500427105, 0.38371645798906684, 0.39661604099092074] │                                                                                  │
│ │ concatenation  │ [1.831420500006061, 1.8045542500040028, 1.8012452079856303]     │                                                                                  │
│ │ exponentiation │ [2.1522245419910178, 2.1751532499911264, 2.2064731669961475]    │                                                                                  │
│ │ multiplication │ [0.4023984170053154, 0.45870250000734814, 0.5052193750161678]   │                                                                                  │
│ │ rangelist      │ [0.10194725001929328, 0.09878037497401237, 0.10006220897776075] │                                                                                  │
│ ╰────────────────┴─────────────────────────────────────────────────────────────────╯                                                                                  │
╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

Run of Doubling Experiment

DLL Queue Implementation
╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│                DLL Queue Doubling Experiment Results                                                                                              │
│ ╭──────────┬──────────┬──────────┬──────────┬──────────┬──────────╮                                                                               │
│ │ Size (n) │  enqueue │  dequeue │     peek │   concat │  iconcat │                                                                               │
│ ├──────────┼──────────┼──────────┼──────────┼──────────┼──────────┤                                                                               │
│ │      100 │ 0.023667 │ 0.006667 │ 0.001916 │ 0.000333 │ 0.000417 │                                                                               │
│ │      200 │ 0.073833 │ 0.013459 │ 0.003500 │ 0.000208 │ 0.000167 │                                                                               │
│ │      400 │ 0.115250 │ 0.024208 │ 0.006083 │ 0.000125 │ 0.000125 │                                                                               │
│ │      800 │ 0.200166 │ 0.048375 │ 0.011542 │ 0.000167 │ 0.000166 │                                                                               │
│ ╰──────────┴──────────┴──────────┴──────────┴──────────┴──────────╯                                                                               │
╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

SLL Queue Implementation
╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│                SLL Queue Doubling Experiment Results                                                                                              │
│ ╭──────────┬──────────┬──────────┬──────────┬──────────┬──────────╮                                                                               │
│ │ Size (n) │  enqueue │  dequeue │     peek │   concat │  iconcat │                                                                               │
│ ├──────────┼──────────┼──────────┼──────────┼──────────┼──────────┤                                                                               │
│ │      100 │ 0.022000 │ 0.005958 │ 0.002292 │ 0.000958 │ 0.000500 │                                                                               │
│ │      200 │ 0.040667 │ 0.011459 │ 0.003500 │ 0.000417 │ 0.000209 │                                                                               │
│ │      400 │ 0.099958 │ 0.020958 │ 0.006125 │ 0.000333 │ 0.000208 │                                                                               │
│ │      800 │ 0.169250 │ 0.041334 │ 0.011708 │ 0.000333 │ 0.000209 │                                                                               │
│ ╰──────────┴──────────┴──────────┴──────────┴──────────┴──────────╯                                                                               │
╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

ARRAY Queue Implementation
╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│               ARRAY Queue Doubling Experiment Results                                                                                             │
│ ╭──────────┬──────────┬──────────┬──────────┬──────────┬──────────╮                                                                               │
│ │ Size (n) │  enqueue │  dequeue │     peek │   concat │  iconcat │                                                                               │
│ ├──────────┼──────────┼──────────┼──────────┼──────────┼──────────┤                                                                               │
│ │      100 │ 0.003791 │ 0.003334 │ 0.002459 │ 0.001833 │ 0.000250 │                                                                               │
│ │      200 │ 0.007083 │ 0.006166 │ 0.004667 │ 0.001917 │ 0.000208 │                                                                               │
│ │      400 │ 0.014125 │ 0.013125 │ 0.009208 │ 0.003375 │ 0.000292 │                                                                               │
│ │      800 │ 0.027542 │ 0.026292 │ 0.017792 │ 0.006417 │ 0.000375 │                                                                               │
│ ╰──────────┴──────────┴──────────┴──────────┴──────────┴──────────╯                                                                               │
╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

Run of Performance Analysis

oetry run analyze analyze                                     

DLL Queue Implementation
╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│              DLL Queue Performance Analysis                                                                                                       │
│ ╭───────────┬───────────┬──────────┬───────────────────╮                                                                                          │
│ │ Operation │ Time (ms) │ Elements │ Time/Element (ms) │                                                                                          │
│ ├───────────┼───────────┼──────────┼───────────────────┤                                                                                          │
│ │ enqueue   │  0.258167 │    1,000 │          0.000258 │                                                                                          │
│ │ dequeue   │  0.060583 │      500 │          0.000121 │                                                                                          │
│ │ peek      │  0.015292 │      333 │          0.000046 │                                                                                          │
│ │ concat    │  0.000334 │      100 │          0.000003 │                                                                                          │
│ │ iconcat   │  0.000417 │      100 │          0.000004 │                                                                                          │
│ ╰───────────┴───────────┴──────────┴───────────────────╯                                                                                          │
╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

SLL Queue Implementation
╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│              SLL Queue Performance Analysis                                                                                                       │
│ ╭───────────┬───────────┬──────────┬───────────────────╮                                                                                          │
│ │ Operation │ Time (ms) │ Elements │ Time/Element (ms) │                                                                                          │
│ ├───────────┼───────────┼──────────┼───────────────────┤                                                                                          │
│ │ enqueue   │  0.196000 │    1,000 │          0.000196 │                                                                                          │
│ │ dequeue   │  0.050458 │      500 │          0.000101 │                                                                                          │
│ │ peek      │  0.014625 │      333 │          0.000044 │                                                                                          │
│ │ concat    │  0.000791 │      100 │          0.000008 │                                                                                          │
│ │ iconcat   │  0.000500 │      100 │          0.000005 │                                                                                          │
│ ╰───────────┴───────────┴──────────┴───────────────────╯                                                                                          │
╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

ARRAY Queue Implementation
╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│             ARRAY Queue Performance Analysis                                                                                                      │
│ ╭───────────┬───────────┬──────────┬───────────────────╮                                                                                          │
│ │ Operation │ Time (ms) │ Elements │ Time/Element (ms) │                                                                                          │
│ ├───────────┼───────────┼──────────┼───────────────────┤                                                                                          │
│ │ enqueue   │  0.043708 │    1,000 │          0.000044 │                                                                                          │
│ │ dequeue   │  0.029083 │      500 │          0.000058 │                                                                                          │
│ │ peek      │  0.019541 │      333 │          0.000059 │                                                                                          │
│ │ concat    │  0.007208 │      100 │          0.000072 │                                                                                          │
│ │ iconcat   │  0.000625 │      100 │          0.000006 │                                                                                          │
│ ╰───────────┴───────────┴──────────┴───────────────────╯                                                                                          │
╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

Anupraj Guragain

Run of systemsense


✨ Displaying System Information

╭─────────────────────────────────────────────────────────────────────────── System Information Panel ───────────────────────────────────────────────────────────────────────────╮
│ ╭──────────────────┬───────────────────────────────────────────────────────────────────────╮                                                                                   │
│ │ System Parameter │ Parameter Value                                                       │                                                                                   │
│ ├──────────────────┼───────────────────────────────────────────────────────────────────────┤                                                                                   │
│ │ battery          │ 77.25% battery life remaining, unknown seconds remaining              │                                                                                   │
│ │ cpu              │ x86_64                                                                │                                                                                   │
│ │ cpucores         │ Physical cores: 4, Logical cores: 8                                   │                                                                                   │
│ │ cpufrequencies   │ Min: 400.0 Mhz, Max: 4400.0 Mhz                                       │                                                                                   │
│ │ datetime         │ 27/03/2025 17:41:34                                                   │                                                                                   │
│ │ disk             │ Using 43.44 GB of 97.87 GB                                            │                                                                                   │
│ │ hostname         │ cislaptop                                                             │                                                                                   │
│ │ memory           │ Using 8.05 GB of 15.35 GB                                             │                                                                                   │
│ │ platform         │ Linux 6.11.0-21-generic                                               │                                                                                   │
│ │ pythonversion    │ 3.12.3                                                                │                                                                                   │
│ │ runningprocesses │ 362                                                                   │                                                                                   │
│ │ swap             │ Total: 4095 MB, Used: 0 MB, Free: 4095 MB                             │                                                                                   │
│ │ system           │ Linux                                                                 │                                                                                   │
│ │ systemload       │ Average Load: 3.07, CPU Utilization: 3.90%                            │                                                                                   │
│ │ virtualenv       │ /home/student/.cache/pypoetry/virtualenvs/systemsense-DC4abhLn-py3.12 │                                                                                   │
│ ╰──────────────────┴───────────────────────────────────────────────────────────────────────╯                                                                                   │
╰────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

🏁 Displaying Benchmark Results

╭───────────────────────────────────────────────────────────────────────── Benchmark Information Panel ──────────────────────────────────────────────────────────────────────────╮
│ ╭────────────────┬─────────────────────────────────────────────────────────────────╮                                                                                           │
│ │ Benchmark Name │ Benchmark Results (sec)                                         │                                                                                           │
│ ├────────────────┼─────────────────────────────────────────────────────────────────┤                                                                                           │
│ │ addition       │ [0.39699050600029295, 0.39876872999593616, 0.40132377600093605] │                                                                                           │
│ │ concatenation  │ [1.9879290609969757, 1.9158207119980943, 1.9231829279960948]    │                                                                                           │
│ │ exponentiation │ [1.9385030220000772, 1.9133422640006756, 2.0385779130010633]    │                                                                                           │
│ │ multiplication │ [0.3794930040021427, 0.3551806879986543, 0.35516838500188896]   │                                                                                           │
│ │ rangelist      │ [0.10307988400018075, 0.0976890980018652, 0.0977334429990151]   │                                                                                           │
│ ╰────────────────┴─────────────────────────────────────────────────────────────────╯                                                                                           │
╰────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

Run of Doubling Experiment


DLL Queue Implementation
╭─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│                DLL Queue Doubling Experiment Results                                                                        │
│ ╭──────────┬──────────┬──────────┬──────────┬──────────┬──────────╮                                                         │
│ │ Size (n) │  enqueue │  dequeue │     peek │   concat │  iconcat │                                                         │
│ ├──────────┼──────────┼──────────┼──────────┼──────────┼──────────┤                                                         │
│ │      100 │ 0.039566 │ 0.011458 │ 0.003488 │ 0.000625 │ 0.000858 │                                                         │
│ │      200 │ 0.113858 │ 0.022507 │ 0.006425 │ 0.000403 │ 0.000311 │                                                         │
│ │      400 │ 0.202240 │ 0.047851 │ 0.012279 │ 0.000379 │ 0.000280 │                                                         │
│ │      800 │ 0.361492 │ 0.094825 │ 0.022960 │ 0.000330 │ 0.000355 │                                                         │
│ ╰──────────┴──────────┴──────────┴──────────┴──────────┴──────────╯                                                         │
╰─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

SLL Queue Implementation
╭─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│                SLL Queue Doubling Experiment Results                                                                        │
│ ╭──────────┬──────────┬──────────┬──────────┬──────────┬──────────╮                                                         │
│ │ Size (n) │  enqueue │  dequeue │     peek │   concat │  iconcat │                                                         │
│ ├──────────┼──────────┼──────────┼──────────┼──────────┼──────────┤                                                         │
│ │      100 │ 0.078195 │ 0.014763 │ 0.003961 │ 0.001582 │ 0.000946 │                                                         │
│ │      200 │ 0.070928 │ 0.019607 │ 0.006181 │ 0.000761 │ 0.000489 │                                                         │
│ │      400 │ 0.176146 │ 0.049838 │ 0.012285 │ 0.000710 │ 0.000490 │                                                         │
│ │      800 │ 0.309921 │ 0.083965 │ 0.024419 │ 0.000687 │ 0.000442 │                                                         │
│ ╰──────────┴──────────┴──────────┴──────────┴──────────┴──────────╯                                                         │
╰─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

ARRAY Queue Implementation
╭─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│               ARRAY Queue Doubling Experiment Results                                                                       │
│ ╭──────────┬──────────┬──────────┬──────────┬──────────┬──────────╮                                                         │
│ │ Size (n) │  enqueue │  dequeue │     peek │   concat │  iconcat │                                                         │
│ ├──────────┼──────────┼──────────┼──────────┼──────────┼──────────┤                                                         │
│ │      100 │ 0.007520 │ 0.006178 │ 0.004555 │ 0.002887 │ 0.000509 │                                                         │
│ │      200 │ 0.013283 │ 0.012204 │ 0.008401 │ 0.002614 │ 0.000355 │                                                         │
│ │      400 │ 0.026229 │ 0.025153 │ 0.016454 │ 0.007943 │ 0.000658 │                                                         │
│ │      800 │ 0.110293 │ 0.075074 │ 0.031935 │ 0.009347 │ 0.000694 │                                                         │
│ ╰──────────┴──────────┴──────────┴──────────┴──────────┴──────────╯                                                         │
╰─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯
Plots saved to results directory

Run of Performance Analysis



DLL Queue Implementation
╭─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│              DLL Queue Performance Analysis                                                                                 │
│ ╭───────────┬───────────┬──────────┬───────────────────╮                                                                    │
│ │ Operation │ Time (ms) │ Elements │ Time/Element (ms) │                                                                    │
│ ├───────────┼───────────┼──────────┼───────────────────┤                                                                    │
│ │ enqueue   │  0.477277 │    1,000 │          0.000477 │                                                                    │
│ │ dequeue   │  0.117047 │      500 │          0.000234 │                                                                    │
│ │ peek      │  0.032079 │      333 │          0.000096 │                                                                    │
│ │ concat    │  0.000720 │      100 │          0.000007 │                                                                    │
│ │ iconcat   │  0.000936 │      100 │          0.000009 │                                                                    │
│ ╰───────────┴───────────┴──────────┴───────────────────╯                                                                    │
╰─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

SLL Queue Implementation
╭─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│              SLL Queue Performance Analysis                                                                                 │
│ ╭───────────┬───────────┬──────────┬───────────────────╮                                                                    │
│ │ Operation │ Time (ms) │ Elements │ Time/Element (ms) │                                                                    │
│ ├───────────┼───────────┼──────────┼───────────────────┤                                                                    │
│ │ enqueue   │  0.411052 │    1,000 │          0.000411 │                                                                    │
│ │ dequeue   │  0.106158 │      500 │          0.000212 │                                                                    │
│ │ peek      │  0.031625 │      333 │          0.000095 │                                                                    │
│ │ concat    │  0.002308 │      100 │          0.000023 │                                                                    │
│ │ iconcat   │  0.001400 │      100 │          0.000014 │                                                                    │
│ ╰───────────┴───────────┴──────────┴───────────────────╯                                                                    │
╰─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

ARRAY Queue Implementation
╭─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│             ARRAY Queue Performance Analysis                                                                                │
│ ╭───────────┬───────────┬──────────┬───────────────────╮                                                                    │
│ │ Operation │ Time (ms) │ Elements │ Time/Element (ms) │                                                                    │
│ ├───────────┼───────────┼──────────┼───────────────────┤                                                                    │
│ │ enqueue   │  0.115217 │    1,000 │          0.000115 │                                                                    │
│ │ dequeue   │  0.069180 │      500 │          0.000138 │                                                                    │
│ │ peek      │  0.044262 │      333 │          0.000133 │                                                                    │
│ │ concat    │  0.012812 │      100 │          0.000128 │                                                                    │
│ │ iconcat   │  0.001020 │      100 │          0.000010 │                                                                    │
│ ╰───────────┴───────────┴──────────┴───────────────────╯                                                                    │
╰─────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

Joseph Oforkansi

Run of systemsense


╭──────────────────────────────────── Displaying System Panel Information ────────────────────────────────────╮
│ ┏━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓              │
│ ┃ System Parameter ┃ Parameter Value                                                         ┃              │
│ ┣━━━━━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫              │
│ ┃ battery          ┃ 49.48% battery life remaining, 3:34:11 seconds remaining                ┃              │
│ ┃ cpu              ┃ x86_64                                                                  ┃              │
│ ┃ cpucores         ┃ Physical cores: 6, Logical cores: 12                                    ┃              │
│ ┃ cpufrequencies   ┃ Min: 0.0 Mhz, Max: 0.0 Mhz                                              ┃              │
│ ┃ datetime         ┃ 2025-03-28 00:07:56                                                     ┃              │
│ ┃ disk             ┃ Total: 1006.85 GB, Used: 4.94 GB, Free: 950.70 GB                       ┃              │
│ ┃ hostname         ┃ Ubasinachi                                                              ┃              │
│ ┃ memory           ┃ Total: 3.55 GB, Available: 2.97 GB, Used: 0.42 GB                       ┃              │
│ ┃ platform         ┃ Linux-5.15.167.4-microsoft-standard-WSL2-x86_64-with-glibc2.39          ┃              │
│ ┃ pythonversion    ┃ 3.12.3                                                                  ┃              │
│ ┃ runningprocesses ┃ 30                                                                      ┃              │
│ ┃ swap             ┃ Total: 1.00 GB, Used: 0.00 GB, Free: 1.00 GB                            ┃              │
│ ┃ system           ┃ Linux                                                                   ┃              │
│ ┃ systemload       ┃ (0.09033203125, 0.02294921875, 0.00537109375)                           ┃              │
│ ┃ virtualenv       ┃ /home/oforkansi/.cache/pypoetry/virtualenvs/systemsense-Rt5TvRuf-py3.12 ┃              │
│ ┗━━━━━━━━━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛              │
╰─────────────────────────────────────────────────────────────────────────────────────────────────────────────╯


Displaying Benchmark Results

╭────────────────────────────────── Displaying Benchmark Panel Information ───────────────────────────────────╮
│ ┏━━━━━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓                         │
│ ┃ Benchmark Name ┃ Benchmark Results (sec)                                        ┃                         │
│ ┣━━━━━━━━━━━━━━━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫                         │
│ ┃ addition       ┃ [0.31629270799749065, 0.3047017440003401, 0.30586198799937847] ┃                         │
│ ┃ concatenation  ┃ [1.252448921000905, 1.2106726849997358, 1.196216729000298]     ┃                         │
│ ┃ exponentiation ┃ [3.4946560460011824, 2.8278707829995255, 2.6028115440021793]   ┃                         │
│ ┃ multiplication ┃ [0.46731175999957486, 0.47331768200092483, 0.4569921219990647] ┃                         │
│ ┃ rangelist      ┃ [0.18792873100028373, 0.1763109790008457, 0.17144616799851065] ┃                         │
│ ┗━━━━━━━━━━━━━━━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛                         │
╰─────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

Run of Doubling Experiment

DLL Queue Implementation
╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│                DLL Queue Doubling Experiment Results                                                          │
│ ╭──────────┬──────────┬──────────┬──────────┬──────────┬──────────╮                                           │
│ │ Size (n) │  enqueue │  dequeue │     peek │   concat │  iconcat │                                           │
│ ├──────────┼──────────┼──────────┼──────────┼──────────┼──────────┤                                           │
│ │      100 │ 0.078146 │ 0.021706 │ 0.005929 │ 0.001395 │ 0.001344 │                                           │
│ │      200 │ 0.204515 │ 0.048069 │ 0.011960 │ 0.000667 │ 0.000349 │                                           │
│ │      400 │ 0.248051 │ 0.056235 │ 0.015726 │ 0.000554 │ 0.000380 │                                           │
│ │      800 │ 0.438154 │ 0.106643 │ 0.029851 │ 0.000493 │ 0.000328 │                                           │
│ ╰──────────┴──────────┴──────────┴──────────┴──────────┴──────────╯                                           │
╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

SLL Queue Implementation
╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│                SLL Queue Doubling Experiment Results                                                          │
│ ╭──────────┬──────────┬──────────┬──────────┬──────────┬──────────╮                                           │
│ │ Size (n) │  enqueue │  dequeue │     peek │   concat │  iconcat │                                           │
│ ├──────────┼──────────┼──────────┼──────────┼──────────┼──────────┤                                           │
│ │      100 │ 0.064944 │ 0.017890 │ 0.007950 │ 0.003057 │ 0.001652 │                                           │
│ │      200 │ 0.216928 │ 0.023132 │ 0.008165 │ 0.001077 │ 0.000482 │                                           │
│ │      400 │ 0.203469 │ 0.047208 │ 0.015469 │ 0.000790 │ 0.000452 │                                           │
│ │      800 │ 0.389417 │ 0.094077 │ 0.078423 │ 0.001128 │ 0.000595 │                                           │
│ ╰──────────┴──────────┴──────────┴──────────┴──────────┴──────────╯                                           │
╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

ARRAY Queue Implementation
╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│               ARRAY Queue Doubling Experiment Results                                                         │
│ ╭──────────┬──────────┬──────────┬──────────┬──────────┬──────────╮                                           │
│ │ Size (n) │  enqueue │  dequeue │     peek │   concat │  iconcat │                                           │
│ ├──────────┼──────────┼──────────┼──────────┼──────────┼──────────┤                                           │
│ │      100 │ 0.014208 │ 0.011386 │ 0.009879 │ 0.006011 │ 0.000964 │                                           │
│ │      200 │ 0.024209 │ 0.053722 │ 0.016782 │ 0.005693 │ 0.000687 │                                           │
│ │      400 │ 0.031636 │ 0.028630 │ 0.063159 │ 0.008494 │ 0.000677 │                                           │
│ │      800 │ 0.102058 │ 0.097903 │ 0.088619 │ 0.022486 │ 0.001354 │                                           │
│ ╰──────────┴──────────┴──────────┴──────────┴──────────┴──────────╯                                           │
╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

Run of Performance Analysis

DLL Queue Implementation
╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│              DLL Queue Performance Analysis                                                                   │
│ ╭───────────┬───────────┬──────────┬───────────────────╮                                                      │
│ │ Operation │ Time (ms) │ Elements │ Time/Element (ms) │                                                      │
│ ├───────────┼───────────┼──────────┼───────────────────┤                                                      │
│ │ enqueue   │  1.033531 │    1,000 │          0.001034 │                                                      │
│ │ dequeue   │  0.136059 │      500 │          0.000272 │                                                      │
│ │ peek      │  0.036996 │      333 │          0.000111 │                                                      │
│ │ concat    │  0.000893 │      100 │          0.000009 │                                                      │
│ │ iconcat   │  0.000914 │      100 │          0.000009 │                                                      │
│ ╰───────────┴───────────┴──────────┴───────────────────╯                                                      │
╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

SLL Queue Implementation
╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│              SLL Queue Performance Analysis                                                                   │
│ ╭───────────┬───────────┬──────────┬───────────────────╮                                                      │
│ │ Operation │ Time (ms) │ Elements │ Time/Element (ms) │                                                      │
│ ├───────────┼───────────┼──────────┼───────────────────┤                                                      │
│ │ enqueue   │  1.117241 │    1,000 │          0.001117 │                                                      │
│ │ dequeue   │  0.232174 │      500 │          0.000464 │                                                      │
│ │ peek      │  0.051571 │      333 │          0.000155 │                                                      │
│ │ concat    │  0.002783 │      100 │          0.000028 │                                                      │
│ │ iconcat   │  0.001448 │      100 │          0.000014 │                                                      │
│ ╰───────────┴───────────┴──────────┴───────────────────╯                                                      │
╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

ARRAY Queue Implementation
╭───────────────────────────────────────────────────────────────────────────────────────────────────────────────╮
│             ARRAY Queue Performance Analysis                                                                  │
│ ╭───────────┬───────────┬──────────┬───────────────────╮                                                      │
│ │ Operation │ Time (ms) │ Elements │ Time/Element (ms) │                                                      │
│ ├───────────┼───────────┼──────────┼───────────────────┤                                                      │
│ │ enqueue   │  0.121895 │    1,000 │          0.000122 │                                                      │
│ │ dequeue   │  0.121803 │      500 │          0.000244 │                                                      │
│ │ peek      │  0.071548 │      333 │          0.000215 │                                                      │
│ │ concat    │  0.085331 │      100 │          0.000853 │                                                      │
│ │ iconcat   │  0.001982 │      100 │          0.000020 │                                                      │
│ ╰───────────┴───────────┴──────────┴───────────────────╯                                                      │
╰───────────────────────────────────────────────────────────────────────────────────────────────────────────────╯

Run of Performance Analysis

Key Finding
  • The Array implementation maintains its O(1) behavior for basic operations even with large data sizes
  • The DLL and SLL implementations show clear O(n) behavior for enqueue operations with large data
  • All implementations show O(1) behavior for peek operations, even with large data
  • The Array implementation’s concatenation operation shows clear O(n) behavior with large data
  • The linked list implementations (DLL and SLL) maintain O(1) behavior for concatenation operations
Final Recommendations:
Use Array Queue

When: - Basic operations (enqueue, dequeue, peek) are the primary operations - Memory efficiency is crucial - Concatenation operations are rare - Fixed or predictable size is expected

Use DLL Queue

When: - Concatenation operations are frequent - Bidirectional traversal is needed - Dynamic size changes are common - Memory overhead is not a concern

Use SLL Queue

When: - Concatenation operations are frequent - Memory efficiency is important - Unidirectional traversal is sufficient - Dynamic size changes are common - Example: Task queue in a scheduler

Conclusion

The choice of queue implementation should be based on the specific requirements of the application: - For applications prioritizing basic operations and memory efficiency, the Array implementation is the best choice - For applications requiring frequent concatenation and dynamic size changes, either DLL or SLL implementation would be more suitable - SLL provides a good balance between memory efficiency and functionality, while DLL offers the most flexibility at the cost of higher memory overhead The performance analysis shows that there is no “one-size-fits-all” solution, and the optimal choice depends on the specific use case and requirements of the application.

Future Works

  • Analyzing performance under varying workloads and larger data sizes
  • Measuring memory usage across different implementations
  • Develops and experiment with hybrid implementations that combine strengths of different approaches
Back to top

Algorithmology