Skip to content

[Performance] O(n) linear search in getColumn() causes bottleneck in batch writes #138

Description

@netmou

When performing batch writes using TableEditor, the getColumn() method is called frequently. However, the current implementation uses a linear foreach loop to search for the column by name, resulting in an O(n) time complexity per call. This causes a significant performance bottleneck when dealing with large datasets.

public function getColumn(string $name): Column
{
    $name = strtolower($name);
    foreach ($this->header->columns as $column) {
        if ($column->name === $name) {
            return $column;
        }
    }
    throw new \Exception("Column $name not found");
}

Every call iterates through the entire $this->header->columns array.
Suggested Solution
To optimize this, I suggest building an associative map (hash map) when the header is initialized or columns are added. This would reduce the lookup time complexity to O(1).

for example:

// When building/initializing the header
protected array $columnMap = [];

public function addColumn(Column $column): void
{
    $this->header->columns[] = $column;
    $this->columnMap[strtolower($column->name)] = $column;
}

public function getColumn(string $name): Column
{
    $name = strtolower($name);
    if (!isset($this->columnMap[$name])) {
        throw new \Exception("Column $name not found");
    }
    return $this->columnMap[$name];
}

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions