-1
\$\begingroup\$

I'm facing the following problem: I have a row of cells. Some cells are available, some are not. Every cell is associated with a cell_id. I want to determine the length of cell. This length of a cell c is defined as the length of the chain c, c1, c2, c2, ... where c1 has the next cell_id after c, c2 has the next cell_id after c1, and so forth.

This length is finite, since at some point there won't be the cell c(n+1) contained in the row of cells.

This is my current function:

def get_cell_length(cell, row):
    if cell not in row:
        return 0

    length = 1
    next_cell_id = get_next_cell_id(cell.get_attribute('id'))

    next_cell_found = True
    while next_cell_found:
        next_cell_found = False
        for next_cell in row:
            if next_cell.get_attribute('id') == next_cell_id:
                length = length + 1
                cell = next_cell
                next_cell_id = get_next_cell_id(cell.get_attribute('id'))
                next_cell_found = True

    return length
  • get_next_cell_id is given the id of a cell c and returns the next cell_id after c.

The input could look like this:

row = [("cell1", 1), ("cell2", 2), ("cell3", 3), ("cell5", 5), ("cell6", 6), ("cell7", 7), ("cell10", 10)]

In this case cell.get_attribute('id') should just return cell[1] and get_next_cell_id(id) would just return id + 1.

The expected output would be:

get_cell_length(("cell1", 1), row) -> 3
get_cell_length(("cell2", 2), row) -> 2
get_cell_length(("cell3", 3), row) -> 1
get_cell_length(("cell6", 5), row) -> 2
get_cell_length(("cell10", 10), row) -> 1

But the function does not look clean to me and seem slow as well. Any help is welcome!

\$\endgroup\$
  • 2
    \$\begingroup\$ can you provide some minimal sample data and expected outcome? \$\endgroup\$ – Maarten Fabré May 29 '18 at 10:58
  • \$\begingroup\$ @MaartenFabré I added some extra information. In my code-example the cells are web-elements from selenium, but I think the example provides all necessary information. \$\endgroup\$ – user7802048 May 29 '18 at 17:55
1
\$\begingroup\$

A lot of why this code looks not so clean to me is because of the clunky Selenium interface (cell.get_attribute('id')) instead of cell['id'] or cell.id for example)

The other reason why this looks lees than clean is because of the flags like next_cell_found instead of using flow control like break and the way you look for the first occurrence of cell

instead of:

if cell not in row:
    return 0

and

while...:
    for next_cell in row:
        if next_cell.get_attribute('id') == next_cell_id:

this can be done in 1 go with:

try:
    idx = row.find(cell)
except ValueError:
    return 0

then you can iterate over the current and next cell at the same time with for current_cell, next_cell in zip(row[idx:], row[idx+1:]):

Checking whether next_cell follows current_cell can best be done in a separate function:

def is_next(cells):
    current_cell, next_cell = cells
    cell_next_id = current_cell[1] + 1
#     cell_next_id = get_next_cell_id(current_cell.get_attribute('id'))
    next_cell_id = next_cell[1]
#     next_cell_id = next_cell.get_attribute('id')
    return cell_next_id == next_cell_id

The commented lines are meant to replace the 'naive' lines preceding them to work with the selenium code as I understand it.

Our total algorithm then becomes:

def get_cell_length(cell, row):
    try:
        idx = row.index(cell)
    except ValueError:
        return 0
    length = 1
    for cells in zip(row[idx:], row[idx+1:]):
        if not is_next(cells):
            break
        length += 1
    return length

iterables

This works if row is a list. If row is a stream or iterable, you will need the help of itertools.dropwhile

from itertools import dropwhile
def get_cell_length_iterable(cell, row):
    row = dropwhile(lambda x: cell != x, row)
    try:
        current_cell = next(row)
    except StopIteration:
        return 0
    length = 1
    for next_cell in row:
        if not is_next((current_cell, next_cell)):
            break
        length += 1
        current_cell = next_cell
    return length
\$\endgroup\$
1
\$\begingroup\$

You should make cell.get_attribute('id') a function that you can pass to get_cell_length.

You want to group your cells together, and so itertools.groupby would be helpful.

From your example all the cells increase in linear order. However they group together when one or more cells are missing. This means if none of the cells are missing then zip(row, itertools.count()) would be the same.

However when a cell is missing it would mean that the number changes. And so we can see this:

\$ \begin{array}{l|l|l|l|l|l|l|l} \text{IDs} & 1& 2& 3& 5& 6& 7& 10\\ \text{expected} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \text{diff} & 1 & 1 & 1 & 2 & 2 & 2 & 4 \\ \end{array} \$

And so we just need to groupby the differences.

After this you want to decrease the size of the group by the index of the cell. And so you can use:

import itertools


def get_cell_length(cell_id, row, get_id):
    r = itertools.count()
    for _, g in itertools.groupby(row, key=lambda i: get_id(i) - next(r)):
        vals = [get_id(i) for i in g]
        if cell_id in vals:
            return len(vals) - vals.index(cell_id)
    return 0

If you plan on using this on the same dataset multiple times you can improve the speed by calculating everything once, and just using a dictionary.

import itertools


def cell_lengths(row, get_id):
    r = itertools.count()
    d = {}
    for _, g in itertools.groupby(row, key=lambda i: get_id(i) - next(r)):
        vals = [get_id(i) for i in g]
        for i, val in enumerate(vals):
            d[val] = len(vals) - i
    return d


d = cell_lengths(row, get_id)
print(d.get(1, 0))
print(d.get(4, 0))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.