Read numbers in line one by one with O(1) space

Viewed 153

Many coding challenges have multiple numbers in the same line, often with a first line telling how many numbers there are in the multi-number line:

4
31 415 9 26

Usually I just read the entire line, then .split() it and map the strings to numbers.

But is there a good way to not read the entire line at once, instead read one number at a time? In order to save memory, either because I can't or don't want to read the whole line into memory. I'd like to only use O(1) space (let's assume numbers are small/bounded so they're O(1) size). Doesn't have to be absolutely minimal, for example if a solution internally reads a full 4 KB memory page at a time, that's ok, still O(1) and relatively small. For use case, think millions of numbers on one line, and a memory limit let's say below 1 MB.

In C++ I'd do it like this:

int n;
std::cin >> n;
while (n--) {
    int value;
    std::cin >> value;
    // now do something with the value
}

I wrote this generator that takes a file object and gives me an iterator of strings. For the above example, it yields the strings '4', '31', '415', '9' and '26'. It reads one character at a time, and splits at space characters as determined by .isspace():

def split(file):
    value = []
    while char := file.read(1):
        if char.isspace():
            if value:
                yield ''.join(value)
            value.clear()
        else:
            value.append(char)
    if value:
        yield ''.join(value)

But that's of course ridiculously complicated and slow, and I don't even know whether this str.isspace usage is equivalent to what str.split considers whitespace. It just illustrates one way to achieve what I want.

Edit: Here's a simpler way, but still more complicated and slow than I'd like. I'm looking for some built-in way that does the low-level work for me, at C speed.

from itertools import groupby

def split(file):
    groups = groupby(iter(lambda: file.read(1), ''), str.isspace)
    for isspace, chars in groups:
        if not isspace:
            yield ''.join(chars)
0 Answers
Related