python - Filtering/Grouping a list of dictionaries by a list of keys -


i need define function, group_dictionaries, take list of dictionaries , return list of dictionaries contain same values each key of list of keys. "lonely" dictionaries deleted.

here example:

my_list=[     {'id':'id1', 'key1':value_x, 'key2': value_y, 'key3':value_z},     {'id':'id3', 'key2 :value_u, 'key3': value_v},     {'id':'id2', 'key1':value_x, 'key3':value_z, 'key4': value_t},     {'id':'id4', 'key1':value_w, 'key2':value_s, 'key3':value_v} ]  group_dictionary(my_list, list_of_keys=['key1', 'key3'])  #result: dictionaries have key1 , key3 in common are: [     {'id':'id1', 'key1':value_x, 'key2': value_y, 'key3':value_z, 'group':0},     {'id':'id2', 'key1':value_x, 'key3':value_z, 'key4': value_t, 'group':0} ]  group_dictionary(my_list, list_of_keys=['key3'])  #result dictionaries have key3 in common divided in 2 groups #of different values: group 0 has value_z , group1 has value_v  [     {'id':'id1', 'key1':value_x, 'key2': value_y, 'key3':value_z, 'group':0},     {'id':'id2', 'key1':value_x, 'key3':value_z, 'key4': value_t, 'group':0},     {'id':'id3', 'key2 :value_u, 'key3': value_v, 'group':1},     {'id':'id4', 'key1':value_w, 'key2':value_s, 'key3':value_v, 'group':1} ]

as can see:

  1. the function creates key labeled 'group' integer starting 0. key assigned each "group" of dictionaries (by group mean dictionaries keys corresponding list of keys match each key)
  2. the function deletes dictionaries don't have "groups".
  3. the existing data set on working contains unique id each dictionary. may useful create function.
  4. non existing keys prevent dictionary being candidate.

i concerned run-time; actual list contains 80,000 dictionaries of 35 keys each in average. complexity of algorithm n² (80,000²). optimization in code welcome.

i believe work, it's written in python3, haven't optimized it, starting point if it's not fast enough. 

list_of_dicts = [ {'id':'id1', 'key1':'value_x', 'key2': 'value_y', 'key3':'value_z'}, {'id':'id3', 'key2' :'value_u', 'key3': 'value_v'}, {'id':'id2', 'key1':'value_x', 'key3':'value_z', 'key4': 'value_t'}, {'id':'id4', 'key1':'value_w', 'key2':'value_s', 'key3':'value_v'} ]  # since can't have objects keys, make values we're looking string, , use key. def make_value_key(d, list_of_keys):     res = ""     k in list_of_keys:         res += str(d[k])      return res  def group_dictionary(list_of_dicts, list_of_keys):     group_vals = {}     current_max_group = 0     dicts_to_remove = []     i,d in enumerate(list_of_dicts):         # if dict doesn't have keys mark removal.         if not all(k in d k in list_of_keys):             dicts_to_remove.append(i)         else:             value_key = make_value_key(d, list_of_keys)             # if value key exists assign group otherwise make new group.             if value_key in group_vals:                 d['group'] = group_vals[value_key]             else:                 group_vals[value_key] = current_max_group                 d['group'] = current_max_group                 current_max_group += 1      list_of_dicts = [i j, in enumerate(list_of_dicts) if j not in dicts_to_remove]     return list_of_dicts  list_of_keys=['key1','key3']  print(group_dictionary(list_of_dicts, list_of_keys)) print() list_of_keys=['key3']  print(group_dictionary(list_of_dicts, list_of_keys))

output:

[{'key3': 'value_z', 'key1': 'value_x', 'group': 0, 'key2': 'value_y', 'id': 'id1'},  {'key3': 'value_z', 'key1': 'value_x', 'key4': 'value_t', 'group': 0, 'id': 'id2'},  {'key3': 'value_v', 'key1': 'value_w', 'group': 1, 'key2': 'value_s', 'id': 'id4'}]  [{'key3': 'value_z', 'key1': 'value_x', 'group': 0, 'key2': 'value_y', 'id': 'id1'},  {'group': 1, 'key3': 'value_v', 'key2': 'value_u', 'id': 'id3'},  {'key3': 'value_z', 'key1': 'value_x', 'key4': 'value_t', 'group': 0, 'id': 'id2'},  {'key3': 'value_v', 'key1': 'value_w', 'group': 1, 'key2': 'value_s', 'id': 'id4'}]

optimization 1:

instead of iterating keys check if exist, instead can fail while making value-key , return empty string, mark dict deletion:

def make_value_key(d, list_of_keys):     res = ""     k in list_of_keys:         if not k in d:             return ""         res += str(d[k])      return res  def group_dictionary(list_of_dicts, list_of_keys):     group_vals = {}     current_max_group = 0     dicts_to_remove = []     i,d in enumerate(list_of_dicts):         value_key = make_value_key(d, list_of_keys)         if value_key == "":             dicts_to_remove.append(i)             continue         if value_key in group_vals:             d['group'] = group_vals[value_key]          else:             group_vals[value_key] = current_max_group             d['group'] = current_max_group             current_max_group += 1      list_of_dicts = [i j, in enumerate(list_of_dicts) if j not in dicts_to_remove]     return list_of_dicts

groups have bigger 1:

this uses second dict keep track of group sizes, , checks whether groups smaller 2 mark them removal.

def make_value_key(d, list_of_keys):     res = ""     k in list_of_keys:         if not k in d:             return ""         res += str(d[k])      return res  def group_dictionary(list_of_dicts, list_of_keys):     group_vals = {}     group_count = {}     current_max_group = 0     indices_to_remove = []     i,d in enumerate(list_of_dicts):         value_key = make_value_key(d, list_of_keys)         if value_key == "":             indices_to_remove.append(i)             continue         if value_key in group_vals:             d['group'] = group_vals[value_key]             # second group member seen, remove count dict.              group_count.pop(d['group'], none)         else:             group_vals[value_key] = current_max_group             d['group'] = current_max_group             # first time seen, add count dict.             group_count[current_max_group] =             current_max_group += 1      indices_to_remove.extend(group_count.values())     return [i j, in enumerate(list_of_dicts) if j not in indices_to_remove]

output:

[{'key2': 'value_y', 'group': 0, 'id': 'id1', 'key1': 'value_x', 'key3': 'value_z'},  {'key4': 'value_t', 'group': 0, 'id': 'id2', 'key1': 'value_x', 'key3': 'value_z'}]  [{'key2': 'value_y', 'group': 0, 'id': 'id1', 'key1': 'value_x', 'key3': 'value_z'}, {'group': 1, 'id': 'id3', 'key2': 'value_u', 'key3': 'value_v'}, {'key4': 'value_t', 'group': 0, 'id': 'id2', 'key1': 'value_x', 'key3': 'value_z'}, {'key2': 'value_s', 'group': 1, 'id': 'id4', 'key1': 'value_w', 'key3': 'value_v'}]

optimization 2:

you can go o(n^2) (loop through dict list once calculate , once delete) o(n*m log m) (loop through dict list once , loop through sorted removed indices):

def make_value_key(d, list_of_keys):     res = ""     k in list_of_keys:         if not k in d:             return ""         res += str(d[k])      return res  def group_dictionary(list_of_dicts, list_of_keys):     group_vals = {}     group_count = {}     current_max_group = 0     indices_to_remove = []     i,d in enumerate(list_of_dicts):         value_key = make_value_key(d, list_of_keys)         if value_key == "":             indices_to_remove.append(i)             continue         if value_key in group_vals:             d['group'] = group_vals[value_key]             # second group member seen, remove count dict.              group_count.pop(d['group'], none)         else:             group_vals[value_key] = current_max_group             d['group'] = current_max_group             # first time seen, add count dict.             group_count[current_max_group] =             current_max_group += 1      indices_to_remove.extend(group_count.values())     index in sorted(indices_to_remove, reverse=true):         del list_of_dicts[index]      return list_of_dicts

Comments

Post a Comment

Popular posts from this blog

How to understand 2 main() functions after using uftrace to profile the C++ program? -

i trying uftrace profile following simple c++ program: #include <iostream> class { public: a() {std::cout << "a created" << std::endl;} ~a() {std::cout << "a destroyed" << std::endl;} }; int main() { a; return 0; } the profile result this: # uftrace a.out created destroyed # duration tid function 2.026 [ 4828] | __cxa_atexit(); [ 4828] | main() { [ 4828] | __static_initialization_and_destruction_0() { 89.397 [ 4828] | std::ios_base::init::init(); 0.768 [ 4828] | __cxa_atexit(); 93.029 [ 4828] | } /* __static_initialization_and_destruction_0 */ 94.425 [ 4828] | } /* main */ [ 4828] | main() { [ 4828] | a::a() { 11.104 [ 4828] | std::operator <<(); 10.825 [ 4828] | std::basic_ostream::operator <<(); 24.514 [ 4828] | } /* a::a */ [ 4828] | a::~a() { 0.978 [ 4828] | ...
Read more

c# - Update a combobox from a presenter (MVP) -

i using mvp in project, new in mvp. have 2 comboboxes. when select option in combobox, combobox should filled new data. this action in presenter. view 'view1' in presenter, , introduced combobox1 , combobox2 properties in 'view1', because need 'datasource', 'displaymember', 'valuemember' , 'refresh()' in method below. but, when using pattern, enough send property like public string combobox2 { { return combobox1.selectedvalue.tosstring(); } } into presenter not whole combobox. how can solve problem? public void onselectedindexchangedcombobox1() { if (view1.combobox1.selectedindex == -1) { return; } datatable dt = tools.getdatatable("a path"); var query = (from o in dt.asenumerable() o.field<string>("afield") == farmerview.combobox1.selectedvalue.tostring() orderby o.field<string>("anotherfield") select...
Read more

How to put a lock and transaction on table using spring 4 or above using jdbcTemplate and annotations like @Transactional? -

i trying put lock on table while writing on table , if happened in between roll-back . trying convert below code lock table test_g1 read; lock table test_g write; -- begin; start transaction; insert test_g1 values(143); insert test_g values(145); select * test_g1; select * test_g; rollback; select * test_g; unlock tables; how convert above code @transactional spring jdbctemplate code? @transactional(rollbackfor={dataaccessexception.class}) public void test(){ jdbctemplate.execute("insert test1 (id, nam) values (4, 'a')"); throw new dataaccessexception("error") { }; } here trying throw error, insert statement should rollback it's not happening . thanks edit-1 attaching code , doing in jdbcdaoimpl.java , mentioned problem comment above test() . app.java package com.cgiri.javabrains.spring4; import org.springframework.beans.factory.annotation.autowired; import org.springframework.context.applic...
Read more