6
\$\begingroup\$

Summary

In a block storage system, new data is written in blocks. We are going to represent the flash memory as one sequential array. We have a list of block writes coming in the form of arrays of size 2: writes[i] = [first_block_written, last_block_written].

Each block has a rewrite limit. If rewrites on a block reach a certain specified threshold we should run a special diagnostic.

Given blockCount (an integer representing the total number of blocks), writes (the list of block-write arrays of size 2), and threshold, your task is to return the list of disjoint block segments, each consisting of blocks that have reached the rewrite threshold. The list of block segments should be sorted in increasing order by their left ends.

Examples

For blockCount = 10, writes = [[0, 4], [3, 5], [2, 6]], and threshold = 2, the output should be blockStorageRewrites(blockCount, writes, threshold) = [[2, 5]].

After the first write, the blocks 0, 1, 2, 3 and 4 were written in once; After the second write, the blocks 0, 1, 2 and 5 were written in once, and the blocks 3 and 4 reached the rewrite threshold; After the final write, the blocks 2 and 5 reached the rewrite threshold as well, so the blocks that should be diagnosed are 2, 3, 4 and 5. Blocks 2, 3, 4 and 5 form one consequent segment [2, 5].

For blockCount = 10, writes = [[0, 4], [3, 5], [2, 6]], and threshold = 3, the output should be blockStorageRewrites(blockCount, writes, threshold) = [[3, 4]]

For blockCount = 10, writes = [[3, 4], [0, 1], [6, 6]], and threshold = 1, the output should be blockStorageRewrites(blockCount, writes, threshold) = [[0, 1], [3, 4], [6, 6]]

Constraints

  • 1 ≤ blockCount ≤ 10**5
  • 0 ≤ writes.length ≤ 10**5
  • writes[i].length = 2
  • 0 ≤ writes[i][0] ≤ writes[i][1] < blockCount

First try

from itertools import groupby

def group_blocks(num_writes, threshold):
    i = 0
    for key, group in groupby(num_writes, lambda x : x >= threshold):
        # This is faster compared to len(list(g))
        length = sum(1 for _ in group)
        if key:
            yield [i, i + length - 1]
        i += length

def blockStorageRewrites(blockCount, writes, threshold):
    num_writes = [0] * blockCount
    for lower, upper in writes:
        for i in range(lower, upper + 1):
            num_writes[i] += 1
    return list(group_blocks(num_writes, threshold))

Here I just do exactly what is asked, I create an array of blockCount size, loop over the writes and lastly group the consecutive ranges with itertoos.groupby

After trying to optimize

I'm not quite sure what the complexity was, but I tried to lessen the load, yet I still didn't pass the TLE constraints

def get_bad_blocks(blockCount, writes, threshold):
    cons = False
    u = l = -1
    for i in range(blockCount):
        count = 0
        for lower, upper in writes:
            if lower <= i <= upper:
                count += 1
            if count >= threshold:
                if not cons:
                    cons = True
                    l = i
                    u = -1
                break
        else:
            u = i - 1
            cons = False

        if u != -1 and l != -1:
            yield [l, u]
            l = -1
    if cons:
        yield [l, i]


def blockStorageRewrites(blockCount, writes, threshold):    
    return list(get_bad_blocks(blockCount, writes, threshold))

Questions

You can review any and all, but preferably I'm looking for answers that:

  • Tell me if my first example is readable
  • I'm less concerned about readability in my second try, and more interested in speed
  • Please ignore the PEP8 naming violations as this is an issue with the programming challenge site
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't think it's possible to give an "answer" addressing the performance issue — your current algorithm is unsalvageable. Consider what would happen in a realistic scenario where blockCount=1000000. The very first thing you'd do is loop for i in range(1000000)! That cannot possibly be part of a valid solution. You need to come up with an algorithm that doesn't take O(blockCount) time. \$\endgroup\$ – Quuxplusone Mar 13 at 15:47
  • \$\begingroup\$ The comment "should be faster compared to len(list(g))" makes me think you should be doing some performance tests :) \$\endgroup\$ – Peilonrayz Mar 13 at 15:51
  • \$\begingroup\$ @Quuxplusone probably, but I fail to see how this can be done without looping over the entire blockcounts... hence the asking for a review. \$\endgroup\$ – Ludisposed Mar 13 at 15:52
  • \$\begingroup\$ @Peilonrayz I have tested that locally, it should be faster because it doesn't have to construct the list as far as I can tell \$\endgroup\$ – Ludisposed Mar 13 at 15:53
  • 2
    \$\begingroup\$ I don't have time to check now, but my guess is that you would want to use a (default)dict with only those blocks that are encountered in writes. If it is a starting block, add +1, if it's the end block, subtract 1. Then go over the values with itertool.accumulate to get the numbers of writes between blocks. \$\endgroup\$ – Georgy Mar 13 at 16:10
6
\$\begingroup\$

First off when you're optimizing code you need to know what to optimize. At first I thought the problem code was not the groupby, but instead the creation of num_writes. And so I changed your code to be able to find the performance of it.

import cProfile
import random

from itertools import groupby

def group_blocks(num_writes, threshold):
    i = 0
    for key, group in groupby(num_writes, lambda x : x >= threshold):
        # This is faster compared to len(list(g))
        length = sum(1 for _ in group)
        if key:
            yield [i, i + length - 1]
        i += length


def build_writes(block_count, writes):
    num_writes = [0] * block_count
    for lower, upper in writes:
        for i in range(lower, upper + 1):
            num_writes[i] += 1
    return num_writes


def blockStorageRewrites(blockCount, writes, threshold):
    num_writes = build_writes(blockCount, writes)
    return list(group_blocks(num_writes, threshold))


block_count = 10**5
writes = []
for _ in range(10**4):
    a = random.randrange(0, block_count)
    b = random.randrange(a, block_count)
    writes.append([a, b])


cProfile.run('blockStorageRewrites(block_count, writes, 10**4)')

Resulting in the following profile:

         200008 function calls in 25.377 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.002    0.002   25.377   25.377 <string>:1(<module>)
   100001    0.019    0.000    0.025    0.000 lus.py:10(<genexpr>)
        1   25.342   25.342   25.342   25.342 lus.py:16(build_writes)
        1    0.000    0.000   25.375   25.375 lus.py:24(blockStorageRewrites)
        1    0.000    0.000    0.033    0.033 lus.py:6(group_blocks)
   100000    0.007    0.000    0.007    0.000 lus.py:8(<lambda>)
        1    0.000    0.000   25.377   25.377 {built-in method builtins.exec}
        1    0.007    0.007    0.033    0.033 {built-in method builtins.sum}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

Changing the code as per Georgy's comment to:

def build_writes(block_count, writes):
    num_writes = dict(enumerate([0] * block_count))
    for lower, upper in writes:
        num_writes[lower] += 1
        num_writes[upper] -= 1
    return list(accumulate(num_writes))

Gets the following profile, which is orders of magnitude faster:

         200011 function calls in 0.066 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.002    0.002    0.066    0.066 <string>:1(<module>)
   100002    0.021    0.000    0.028    0.000 lus.py:10(<genexpr>)
        1    0.025    0.025    0.025    0.025 lus.py:16(build_writes)
        1    0.003    0.003    0.064    0.064 lus.py:24(blockStorageRewrites)
        2    0.000    0.000    0.036    0.018 lus.py:6(group_blocks)
   100000    0.008    0.000    0.008    0.000 lus.py:8(<lambda>)
        1    0.000    0.000    0.066    0.066 {built-in method builtins.exec}
        2    0.008    0.004    0.036    0.018 {built-in method builtins.sum}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
\$\endgroup\$
  • 1
    \$\begingroup\$ The return list(accumulate(num_writes)) line should be return list(accumulate(num_writes.values())) else I'd be accumulating the keys. Other then that, this is a great teaching moment for me. I should know what the bottlenecks are before optimization :) \$\endgroup\$ – Ludisposed Mar 14 at 8:13
  • 1
    \$\begingroup\$ And I did had to do (block_count + 1) and num_writes[upper + 1] -= 1 to make the upper bound work correctly \$\endgroup\$ – Ludisposed Mar 14 at 8:17
  • \$\begingroup\$ @Ludisposed Ah oops :( My main aim was to show how to go about improving performance, so I didn't test at all. \$\endgroup\$ – Peilonrayz Mar 14 at 14:06
  • \$\begingroup\$ No problem, as the "You should have profiled the code before starting to optimize" was the (for me) important part of the answer. I do wonder did you find any other mistakes, simplifications or just quit after profiling? \$\endgroup\$ – Ludisposed Mar 14 at 14:14
  • 1
    \$\begingroup\$ @Ludisposed I quit after profiling, but the first code looks good otherwise. If there wasn't a TLE then I'd say the original code is good and say to stop there. If there's another TLE then I'd look into it more, but I think 25 seconds -> 0.5 would mean there isn't one. \$\endgroup\$ – Peilonrayz Mar 14 at 14:19

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.