4 ms·

It's a lot faster if you use python's itertools and operator itemgetter: def gen_stats(data): start = time.time() stats = [] data.sort(key=itemge

It's a lot faster if you use python's itertools and operator itemgetter: def gen_stats(data): start = time.time() stats = [] data.sort(key=itemgetter(0)) for p_id, p_items in itertools.groupby(data, key=itemgetter(0)): num_orders, _, total_quantity, total_price = map(sum, zip(*p_items)) p_id, num_orders, total_quantity = map(int, [p_id, num_orders/p_id, total_quantity]) stats.append([p_id, num_orders, total_quantity, round(float(total_price/num_orders),2)]) end = time.time() working_time = end-start return stats, working_time Results: Dataset size 55096 records [[1, 8, 340, 22.55], [2, 4, 94, 15.83], [3, 2, 97, 3.89]] [[1, 8, 340, 22.55], [2, 4, 94, 15.83], [3, 2, 97, 3.89]] All results equal: True Runtime (s) gen_stats_slow: 28.489468574523926 gen_stats_fast: 0.06000018119812012

Radim 9y ago
That doesn't look faster -- 60ms? Nor clearer, at least to me :) Additionally, you might have a bug in the code: groupby() only groups consecutive keys, so your code will fail if the dataset is not already sorted by product_id. I guess that's the lesson here -- use pandas to make sure you get a sane, fast, tested implementation of some common use-cases. That is, if you can remember its API, when it makes copies vs views under the hood, and all that gnarly stuff :-)
eesmith 9y ago
Wee! Pointless optimization Saturday! Looks like my gen_stats_eesmith is even faster. Radim's is about 400x faster, iClaudiusX is 450x faster, and eesmith is 580x faster. Under pypy2-v5.8.0 those are 65x, 16x, and 91x, respectively. The original algorithm is 10x faster under pypy. def gen_stats_python(dataset_python): start = time.time() product_stats = [] unique_products = set([x[0] for x in dataset_python]) for product_id in unique_products: product_items = [x for x in dataset_python if x[0]==product_id ] num_orders = len(product_items) total_quantity = 0 total_price = 0 for row in product_items: total_quantity += row[2] total_price += row[3] avg_price = float(total_price/num_orders) product_stats.append([int(product_id),int(num_orders),int(total_quantity),round(avg_price,2)]) end = time.time() working_time = end-start return product_stats,working_time def gen_stats_radim(dataset_python): start = time.time() aggr = {} for product_id, product_order_num, quantity, price in dataset_python: item = aggr.get(product_id, [0, []]) item[0] += quantity item[1].append(price) aggr[product_id] = item return [ [int(product_id), len(prices), int(quantity), round(float(sum(prices)) / len(prices), 2)] for product_id, (quantity, prices) in aggr.items() ], time.time()-start def gen_stats_iclaudiusx(data): start = time.time() stats = [] data.sort(key=itemgetter(0)) for p_id, p_items in itertools.groupby(data, key=itemgetter(0)): num_orders, _, total_quantity, total_price = map(sum, zip(*p_items)) p_id, num_orders, total_quantity = map(int, [p_id, num_orders/p_id, total_quantity]) stats.append([p_id, num_orders, total_quantity, round(float(total_price/num_orders),2)]) end = time.time() working_time = end-start return stats, working_time def gen_stats_eesmith(dataset_python): start = time.time() product_stats = [] total_num_orders = defaultdict(int) total_quantity_by_product_id = defaultdict(int) total_price_by_product_id = defaultdict(float) for product_id, order_id, quantity, price in dataset_python: total_num_orders[product_id] += 1 total_quantity_by_product_id[product_id] += quantity total_price_by_product_id[product_id] += price for product_id in total_price_by_product_id: num_orders = total_num_orders[product_id] total_quantity = total_quantity_by_product_id[product_id] total_price = total_price_by_product_id[product_id] avg_price = float(total_price)/num_orders product_stats.append([int(product_id),int(num_orders),int(total_quantity),round(avg_price,2)]) end = time.time() working_time = end-start return product_stats,working_time reference_result = reference_dt = None gen_stats_functions = (gen_stats_python, gen_stats_radim, gen_stats_iclaudiusx, gen_stats_eesmith) for gen_stats_function in gen_stats_functions: result, dt = gen_stats_function(dataset_python) if reference_result is None: reference_result = result reference_dt = dt assert result == reference_result, (gen_stats_function.__name__, result[:2], reference_result[:2]) print(gen_stats_function.__name__, dt, reference_dt/dt)
- Radim 9y ago
  Nice :) Interestingly, the O(n) Python is still about 4x slower than the O(n) Pandas -- the same relative difference as in the original O(n^2) implementations from the blog post. So despite the mishaps of this "Senior IT Business Analyst" choosing an unsuitable algorithm, his relative graphs pretty much stand.
  - lukasz_km 9y ago
    I have had much fun reading this thread of comments today :) This comparison was never about concrete (optimal) implementations but about comparing exactly the same implementations, doing exactly the same operations. Such approach would be the same for comparing performance of any languages, like C and Java. This is not "the best algo" race. So, after a day of discussion, the result is the following: regardless if the implementation is quadratic or linear, the relative speed of all 3 technologies is (roughly) the same. I could not agree more as this is primary school math: dividing by the same denominator still means that proportions are the same :) I plan to update my blog post, based on many interesting comments you have all provided. I definetely think this analysis should be more complex. Thank you for your insights. I have many great pieces of code for inspiration, but I am struggling with providing exactly the same implementations. So it may cost me some time to provide all 3 optimized implementations that are exactly relevant to each other.
    - eesmith 9y ago
      "the relative speed of all 3 technologies is (roughly) the same" I'll be a bit pedantic. The original essay says "pure Python", which is not a technology but a language. There are several implementations of Python, which I'll argue is the "technology". The PyPy implementation of the pure Python algorithm is 10x faster than the CPython implementation. According to the original essay, that's close to the CPython/NumPy performance, and faster than the CPython/Pandas version. It's tempting to omit PyPy because "nobody uses it in data science". That's a self-fulfilling argument. PyPy is doing amazing work to support both NumPy and Pandas, but it's limited by funding. Why aren't data science people pumping money into PyPy? It would give a huge performance boost even for naive, throw-it-together algorithms. If you don't know why PyPy can do for you, how do you learn if/when you should use it?

Radim 9y ago

That doesn't look faster -- 60ms? Nor clearer, at least to me :) Additionally, you might have a bug in the code: groupby() only groups consecutive keys, so your code will fail if the dataset is not already sorted by product_id. I guess that's the lesson here -- use pandas to make sure you get a sane, fast, tested implementation of some common use-cases. That is, if you can remember its API, when it makes copies vs views under the hood, and all that gnarly stuff :-)

eesmith 9y ago

Wee! Pointless optimization Saturday! Looks like my gen_stats_eesmith is even faster. Radim's is about 400x faster, iClaudiusX is 450x faster, and eesmith is 580x faster. Under pypy2-v5.8.0 those are 65x, 16x, and 91x, respectively. The original algorithm is 10x faster under pypy. def gen_stats_python(dataset_python): start = time.time() product_stats = [] unique_products = set([x[0] for x in dataset_python]) for product_id in unique_products: product_items = [x for x in dataset_python if x[0]==product_id ] num_orders = len(product_items) total_quantity = 0 total_price = 0 for row in product_items: total_quantity += row[2] total_price += row[3] avg_price = float(total_price/num_orders) product_stats.append([int(product_id),int(num_orders),int(total_quantity),round(avg_price,2)]) end = time.time() working_time = end-start return product_stats,working_time def gen_stats_radim(dataset_python): start = time.time() aggr = {} for product_id, product_order_num, quantity, price in dataset_python: item = aggr.get(product_id, [0, []]) item[0] += quantity item[1].append(price) aggr[product_id] = item return [ [int(product_id), len(prices), int(quantity), round(float(sum(prices)) / len(prices), 2)] for product_id, (quantity, prices) in aggr.items() ], time.time()-start def gen_stats_iclaudiusx(data): start = time.time() stats = [] data.sort(key=itemgetter(0)) for p_id, p_items in itertools.groupby(data, key=itemgetter(0)): num_orders, _, total_quantity, total_price = map(sum, zip(*p_items)) p_id, num_orders, total_quantity = map(int, [p_id, num_orders/p_id, total_quantity]) stats.append([p_id, num_orders, total_quantity, round(float(total_price/num_orders),2)]) end = time.time() working_time = end-start return stats, working_time def gen_stats_eesmith(dataset_python): start = time.time() product_stats = [] total_num_orders = defaultdict(int) total_quantity_by_product_id = defaultdict(int) total_price_by_product_id = defaultdict(float) for product_id, order_id, quantity, price in dataset_python: total_num_orders[product_id] += 1 total_quantity_by_product_id[product_id] += quantity total_price_by_product_id[product_id] += price for product_id in total_price_by_product_id: num_orders = total_num_orders[product_id] total_quantity = total_quantity_by_product_id[product_id] total_price = total_price_by_product_id[product_id] avg_price = float(total_price)/num_orders product_stats.append([int(product_id),int(num_orders),int(total_quantity),round(avg_price,2)]) end = time.time() working_time = end-start return product_stats,working_time reference_result = reference_dt = None gen_stats_functions = (gen_stats_python, gen_stats_radim, gen_stats_iclaudiusx, gen_stats_eesmith) for gen_stats_function in gen_stats_functions: result, dt = gen_stats_function(dataset_python) if reference_result is None: reference_result = result reference_dt = dt assert result == reference_result, (gen_stats_function.__name__, result[:2], reference_result[:2]) print(gen_stats_function.__name__, dt, reference_dt/dt)

Radim 9y ago
Nice :) Interestingly, the O(n) Python is still about 4x slower than the O(n) Pandas -- the same relative difference as in the original O(n^2) implementations from the blog post. So despite the mishaps of this "Senior IT Business Analyst" choosing an unsuitable algorithm, his relative graphs pretty much stand.
- lukasz_km 9y ago
  I have had much fun reading this thread of comments today :) This comparison was never about concrete (optimal) implementations but about comparing exactly the same implementations, doing exactly the same operations. Such approach would be the same for comparing performance of any languages, like C and Java. This is not "the best algo" race. So, after a day of discussion, the result is the following: regardless if the implementation is quadratic or linear, the relative speed of all 3 technologies is (roughly) the same. I could not agree more as this is primary school math: dividing by the same denominator still means that proportions are the same :) I plan to update my blog post, based on many interesting comments you have all provided. I definetely think this analysis should be more complex. Thank you for your insights. I have many great pieces of code for inspiration, but I am struggling with providing exactly the same implementations. So it may cost me some time to provide all 3 optimized implementations that are exactly relevant to each other.
  - eesmith 9y ago
    "the relative speed of all 3 technologies is (roughly) the same" I'll be a bit pedantic. The original essay says "pure Python", which is not a technology but a language. There are several implementations of Python, which I'll argue is the "technology". The PyPy implementation of the pure Python algorithm is 10x faster than the CPython implementation. According to the original essay, that's close to the CPython/NumPy performance, and faster than the CPython/Pandas version. It's tempting to omit PyPy because "nobody uses it in data science". That's a self-fulfilling argument. PyPy is doing amazing work to support both NumPy and Pandas, but it's limited by funding. Why aren't data science people pumping money into PyPy? It would give a huge performance boost even for naive, throw-it-together algorithms. If you don't know why PyPy can do for you, how do you learn if/when you should use it?