-1

I have a dictionary d with around 500 main keys (name1, name2, etc.). Each value is itself a small dictionary with 5 keys called ppty1, ppty2, etc.), and the corresponding values are floats converted to strings.

I want to extract data faster than I presently do, based on a list of lists of the form ['name1', 'ppty3','ppty4'] (name1 could by any other nameX and ppty3 and ppty4 could be any other pptyX).

In my application, I have many dictionaries, but they differ only by the values of the fields ppty1, ..., ppty5. All the keys are "static". I do not care if there are some preliminary operations, I would just like the processing time of one dictionary to be, ideally, much faster than now. My poor implementation, consisting in looping over every field takes about 3 ms.

Here is the code to generate d and fields; this is just to simulate dummy data, it does not need to be improved:

import random
random.seed(314)

# build dictionary
def make_small_dict():
    d = {}
    for i in range(5):
        key = "ppty" + str(i)
        d[key] = str(random.random())
    return d

d = {}
for i in range(100):
    d["name" + str(i)] = make_small_dict()

# build fields
def make_row():
    line = ['name' + str(random.randint(0,100))]
    [line.append('ppty' + str(random.randint(0,5))) for i in range(2)]
    return line

fields = [0]*300
for i in range(300):
    fields[i] = [make_row() for j in range(3)]

For example, fields[0] returns

[['name420', 'ppty1', 'ppty1'],
 ['name206', 'ppty1', 'ppty2'],
 ['name21', 'ppty2', 'ppty4']]

so the first row of the output should be something like

[[d['name420']['ppty1'], d['name420']['ppty1'],
 [d['name206']['ppty1'], d['name206']['ppty2']],
 [d['name21']['ppty2'], d['name21']['ppty4']]]]

My solution:

start = time.time()
data = [0] * len(fields)
i = 0
for field in fields:
    data2 = [0] * 3
    j = 0
    for row in field:
        lst = [d[row[0]][key] for key in [row[1], row[2]]]
        data2[j] = lst
        j += 1
    data[i] = data2
    i += 1
print time.time() - start

My main question is, how to do improve my code? Few additional question:

  • Later, I need to do some operations such as column extraction, basic operation on some entries of data: would you recommend storing the extracted values directly in an np.array?
  • How to avoid extracting the same values multiple times (fields has some redundant rows such as ['name1', 'ppty3', 'ppty4'])?
  • I read that things such as i += 1 take a little bit of time, how can I avoid them?
7
  • 1
    You really want to do it "as fast as possible"? Is there a good reason for that? If so, you should probably write a C extension that accesses the dict through the C API. And depending on the dict's load, it may in fact be faster to iterate the table storage manually (it isn't exposed through the public API, but you can cast pointers around to get there). Also, you probably want to split the table into chunks and handle each chunk on a different core. Or did you not actually want to do it as fast as possible, just improve your algorithm so it's fast enough to be reasonable?
    – abarnert
    Mar 14, 2018 at 17:52
  • 2
    sounds like premature optimizing to me. Dicts are fast: O(1) fast. You are not showing your performance-test-code. Why do you need to search? Dont you know the keys? did you print out something in your tests? if so that is a major performance killer - console printing takes AGES. Mar 14, 2018 at 18:43
  • @abarnert By "fast as possible", I mean, "as fast as possible using reasonably common methods", so you are right, if it faster than, say 1ms, then I'd be happy. I'll edit to clarify this point.
    – anderstood
    Mar 14, 2018 at 18:44
  • 1
    @PatrickArtner By "search" I meant extracting the values. I'll add my test code soon (it does not include prints).
    – anderstood
    Mar 14, 2018 at 18:46
  • 1
    Since you're already doing very questionable micro-optimizations like doing append calls for side-effects inside a listcomp, a trivial microoptimization that also makes the code nicer is replacing all those 'name' + str(i) with string formatting. For example, in a quick test on my laptop, your version takes a couple orders of magnitude longer than 'name %d' % (i,), for almost 5x as much savings as using a listcomp in place of a for statement. (Although I doubt either one actually matters here.)
    – abarnert
    Mar 14, 2018 at 18:58

1 Answer 1

1

This was tough to read, so I started by breaking bits out into functions. Then I could test to see if that worked using just a list comprehension. It's already faster, comparison over 10000 runs with timeit showed this code runs in about 64% of the original code's time.

In this case I kept everything in lists to force execution so it is directly comparable, but you could use generators or map, and that'd push the computation back to when the data is actually consumed.

def row_lookup(name, key1, key2):
     return (d[name][key1], d[name][key2]) # Tuple is faster to construct than list

def field_lookup(field):
    return [row_lookup(*row) for row in field]

start = time.time()
result = [field_lookup(field) for field in fields]
print(time.time() - start)
print(data == result)

# without dupes in fields
from itertools import groupby
result = [field_lookup(field) for field, _ in groupby(fields)]

Change just the result assignment line to:

result = map(field_lookup, fields)

And the runtime becomes negligible, because map is a generator, so it's not actually going to compute the data until you ask it for the result. This is not a fair comparison, but if you're not going to consume all the data, you'd save time. Change the list comprehensions in the functions to generators and you'd get the same benefit there too. Multiprocessing and asyncio didn't improve performance time in this case.

If you can change the structure you can preprocess your fields into a list of just the rows [['namex', 'pptyx', 'pptyX']..]. In this case, you can change it to just a single list comprehension, which lets you get this down to about 29% of the original runtime, ignoring the preprocessing to slim the fields.

from itertools import groupby, chain
slim_fields = [row for row, _ in groupby(chain.from_iterable(fields))]
results = [(d[name][key1], d[name][key2]) for name, key1, key2 in slim_fields]

In this case, results is just a list of tuples containing the values: [(value1, value2)..]

6
  • So you think it is not possible to be much faster? It must be possible to speed up a bit more by fetching each row once (fields has duplicate rows), and rebuilding the result using a previously "correspondence table". I don't know how to do that, I'll try.
    – anderstood
    Mar 14, 2018 at 21:29
  • You'll need to test on real data, removing dupes takes time, so it may not be faster. I've included a method to remove the dupes, runs in about 70% time on test data. For much faster, look to Cython or C extension, or generators depending on how the data is then used.
    – Paul Brown
    Mar 14, 2018 at 21:45
  • You'll need to test on real data, removing dupes takes time, so it may not be faster. Yes but I can do that in a preliminary step; as I tried to explain, only the values change, so I can prepare the extraction before. I know where to get each element of result before. That's why I was hoping for a much faster solution, taking advantage of the fact that all the dictionaries I want to extract from differ only by the values, but not the keys.
    – anderstood
    Mar 14, 2018 at 21:50
  • Do you need to keep the data in the same structure?
    – Paul Brown
    Mar 14, 2018 at 22:01
  • I added a structure changing method that is faster. Even if you include the timing of the preprocessing this is still twice as fast as the original.
    – Paul Brown
    Mar 14, 2018 at 22:15

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.