Consistancy of pairs in python

2022-05-04 09:43 Omroth imported from Stackoverflow

I have two lists of the same length, and I wish to find out what percentage of all possible pairs of list indices' values have the same relationship for the two lists, in my case greater than (or sign(list[index_1] - list[index_2])).

Here is my slow implementation:

from itertools import combinations
import random
import numpy as np

values_lists = []
for i in range(4):
    value_list = []
    for j in range(50):
        value_list.append(random.random())
    values_lists.append(value_list)
#

total = 0.
n = 0

for list_1, list_2 in combinations(values_lists, 2):
    for index_1, index_2 in combinations(range(len(list_1)), 2):
        if np.sign(list_1[index_2] - list_1[index_1]) == np.sign(list_2[index_2] - list_2[index_1]):
            total += 1
        
        n += 1

print(total / n)

I'm wondering if anyone has a faster solution, as this takes some time.

3 answers

answered 2022-05-04 11:02 Kelly Bundy

Precomputing the signs for each list (and not using NumPy) makes it about 14 times faster (solution2), and doing the same with mostly NumPy makes it about 48 times faster (solution3).

11.52 ms  solution1
 0.82 ms  solution2
 0.25 ms  solution3

11.35 ms  solution1
 0.81 ms  solution2
 0.24 ms  solution3

11.42 ms  solution1
 0.83 ms  solution2
 0.26 ms  solution3

Code (Try it online!):

def solution1(values_lists):
    total = 0.
    n = 0

    for list_1, list_2 in combinations(values_lists, 2):
        for index_1, index_2 in combinations(range(len(list_1)), 2):
            if np.sign(list_1[index_2] - list_1[index_1]) == np.sign(list_2[index_2] - list_2[index_1]):
                total += 1
            n += 1
    return total / n

def solution2(values_lists):
    signs_lists = [
        [-1 if a < b else 1 if b < a else 0
         for a, b in combinations(lst, 2)]
        for lst in values_lists
    ]
    total = 0.
    n = 0
    for signs_1, signs_2 in combinations(signs_lists, 2):
        n += len(signs_1)
        for sign_1, sign_2 in zip(signs_1, signs_2):
            if sign_1 == sign_2:
                total += 1
    return total / n

def solution3(values_lists):
    triu_indices = np.triu_indices(len(values_lists[0]), 1)
    signs_arrays = [
        prod_signs[triu_indices]
        for lst in values_lists
        for a in [np.array(lst)]
        for prod_signs in [np.sign(np.subtract.outer(a, a))]
    ]
    total = 0
    n = 0
    for signs1, signs2 in combinations(signs_arrays, 2):
        n += signs1.size
        total += (signs1 == signs2).sum()
    return total / n

funcs = solution1, solution2, solution3

from timeit import repeat
from itertools import combinations
from operator import eq
import random
import numpy as np

values_lists = []
for i in range(4):
    value_list = []
    for j in range(50):
        value_list.append(random.random())
    values_lists.append(value_list)

for func in funcs:
    print(func(values_lists))

for _ in range(3):
    print()
    for func in funcs:
        t = min(repeat(lambda: func(values_lists), number=10)) / 10
        print('%5.2f ms ' % (t * 1e3), func.__name__)

answered 2022-05-04 11:04 Mike Pennington

I think the best help I can offer is with formatting and organization. You should break your functions into pieces that operate independently.

I also simplified your nested list builder to use a list comprehension.

This doesn't address your code speed concerns, but I couldn't find anything slow when I run the script in question...

from itertools import combinations
import random
import numpy as np
from loguru import logger

@logger.catch
def build_nested_lists(inner_list_size=50, outer_list_size=4):
    values_lists = []
    for ii in range(outer_list_size):
        value_list = [random.random() for jj in range(inner_list_size)]
        values_lists.append(value_list)
    return values_lists


@logger.catch
def handle_nested_lists(
    values_lists=None,
):
    assert isinstance(values_lists, (list, tuple))
    total = 0.0
    n = 0

    for list_1, list_2 in combinations(values_lists, 2):
        for index_1, index_2 in combinations(range(len(list_1)), 2):
            if np.sign(list_1[index_2] - list_1[index_1]) == np.sign(
                list_2[index_2] - list_2[index_1]
            ):
                total += 1
            n += 1
    return total / n

if __name__=="__main__":
    print(handle_nested_lists(build_nested_lists(50, 4)))

answered 2022-05-04 12:00 Nin17

Expanding on @Kelly Bundy 's answer, you can make solution2 even faster by summing a generator expression rather than the nested for loop:

def generatorway():
    signs_lists = (
        [-1 if a < b else 1 if b < a else 0
         for a, b in combinations(lst, 2)]
        for lst in values_lists)
    combos = list(combinations(signs_lists, 2))
    n = sum(len(i) for i, _ in combos)
    total = sum(1 for i, j in combos for k, m in zip(i, j) if k==m)
    return total/n

Speed comparison with values_lists = [[random.random() for _ in range(500)] for _ in range(4)]:

print(generatorway())
print(solution2())
%timeit generatorway()
%timeit solution2()

Output:

0.4931048764195057
0.4931048764195057
66.9 ms ± 58.5 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
68.6 ms ± 38.6 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

See also questions close to this topic

Python File Tagging System does not retrieve nested dictionaries in dictionary

I am building a file tagging system using Python. The idea is simple. Given a directory of files (and files within subdirectories), I want to filter them out using a filter input and tag those files with a word or a phrase.

If I got the following contents in my current directory:

data/
   budget.xls
   world_building_budget.txt
a.txt
b.exe
hello_world.dat
world_builder.spec

and I execute the following command in the shell:

py -3 tag_tool.py -filter=world -tag="World-Building Tool"

My output will be:

These files were tagged with "World-Building Tool":
data/ world_building_budget.txt
hello_world.dat
world_builder.spec

My current output isn't exactly like this but basically, I am converting all files and files within subdirectories into a single dictionary like this:

def fs_tree_to_dict(path_):
    file_token = ''
    for root, dirs, files in os.walk(path_):
        tree = {d: fs_tree_to_dict(os.path.join(root, d)) for d in dirs}
        tree.update({f: file_token for f in files})
        return tree

Right now, my dictionary looks like this: key:''.

In the following function, I am turning the empty values '' into empty lists (to hold my tags):

def empty_str_to_list(d):
    for k,v in d.items():
        if v == '':
            d[k] = []
        elif isinstance(v, dict):
            empty_str_to_list(v)

When I run my entire code, this is my output:

hello_world.dat ['World-Building Tool']
world_builder.spec ['World-Building Tool']

But it does not see data/world_building_budget.txt. This is the full dictionary:

{'data': {'world_building_budget.txt': []},  
'a.txt': [],
'hello_world.dat': [], 
'b.exe': [], 
'world_builder.spec': []}

This is my full code:

import os, argparse


def fs_tree_to_dict(path_):
    file_token = ''
    for root, dirs, files in os.walk(path_):
        tree = {d: fs_tree_to_dict(os.path.join(root, d)) for d in dirs}
        tree.update({f: file_token for f in files})
        return tree


def empty_str_to_list(d):
    for k, v in d.items():
        if v == '':
            d[k] = []
        elif isinstance(v, dict):
            empty_str_to_list(v)


parser = argparse.ArgumentParser(description="Just an example", formatter_class=argparse.ArgumentDefaultsHelpFormatter)

parser.add_argument("--filter", action="store", help="keyword to filter files")
parser.add_argument("--tag", action="store", help="a tag phrase to attach to a file")
parser.add_argument("--get_tagged", action="store", help="retrieve files matching an existing tag")

args = parser.parse_args()

filter = args.filter
tag = args.tag
get_tagged = args.get_tagged
current_dir = os.getcwd()

files_dict = fs_tree_to_dict(current_dir)
empty_str_to_list(files_dict)

for k, v in files_dict.items():
    if filter in k:
        if v == []:
            v.append(tag)
            print(k, v)

        elif isinstance(v, dict):
            empty_str_to_list(v)

    if get_tagged in v:
        print(k, v)

Actaully i am working on a project and in it, it is showing no module name pip_internal plz help me for the same. I am using pycharm(conda interpreter

 File "C:\Users\pjain\AppData\Local\Programs\Python\Python310\lib\runpy.py", line 196, in _run_module_as_main
    return _run_code(code, main_globals, None,
  File "C:\Users\pjain\AppData\Local\Programs\Python\Python310\lib\runpy.py", line 86, in _run_code
    exec(code, run_globals)
  File "C:\Users\pjain\AppData\Local\Programs\Python\Python310\Scripts\pip.exe\__main__.py", line 4, in <module>
  File "C:\Users\pjain\AppData\Local\Programs\Python\Python310\lib\site-packages\pip\_internal\__init__.py", line 4, in <module>
    from pip_internal.utils import _log

I am using pycharm with conda interpreter.

Looping the function if the input is not string

I'm new to python (first of all) I have a homework to do a function about checking if an item exists in a dictionary or not.

inventory = {"apple" : 50, "orange" : 50, "pineapple" : 70, "strawberry" : 30}

def check_item():
    x = input("Enter the fruit's name: ")
    if not x.isalpha():
        print("Error! You need to type the name of the fruit")
    elif x in inventory:
        print("Fruit found:", x)
        print("Inventory available:", inventory[x],"KG")
    else:
        print("Fruit not found")
check_item()

I want the function to loop again only if the input written is not string. I've tried to type return Under print("Error! You need to type the name of the fruit") but didn't work. Help

suggestions on fulltext search or already existing search algorithms
Can someone suggest how to solve the below seach problem easily, I mean is there any algorithm, or full text search will be suffice for this?

There is below classification of items data,
```
ItemCategory        ItemCluster     ItemSubCluster      SubCluster  Items
Vegetable       Root vegetables     Root            WithOutSkin potato, sweet potato, yam
Vegetable       Root vegetables     Root            WithSkin    onion, garlic, shallot
Vegetable       Greens          Leafy green     Leaf        lettuce, spinach, silverbeet
Vegetable       Greens          Cruciferous         Flower      cabbage, cauliflower, Brussels sprouts, broccoli
Vegetable       Greens          Edible plant stem   Stem        celery, asparagus
```
The inputs will be some thing like,

sweet potato, yam Yam, Potato garlik, onion lettuce, spinach, silverbeet lettuce, silverbeet lettuce, silverbeet, spinach

From the input, I want to get the mapping of the input items those belongs to which ItemCategory, ItemCluster, ItemSubCluster, SubCluster.

Any help will be much appreciated.
create string r using string p and q, C++, Data Structures, Strings

In this question we have given 3 strings and we nee dto count possible number of ways to create string r using string p and q
Writing multithreaded code to generate incremental index

I want to write a code in following scenario : we want to design an invoice generator.this invoice generator also generates an incremental invoice no .Also note that for some reasons we dont use something like sql Auto Increment here and we want to use C# (I wrote the increment logic). since several users can send requests at a time it means that we dont have to give the same invoice no to them (I used lock for it and I wrote it).

Now i have written increment logic. and i take care of multiple users requests with lock . and I wrote CRUD for mongodb database.

My problem is that my increent logic is naive. each time i find maximum and i increment by one which is not scalable. and another problem is that when we delete a record we don't want the invoice no to be repeated and since we find max if the deleted record had the max value then the invoice no would be duplicate and this is something we don't want to have.

I really don't know how to handle the problem. specially in case of deletion should i store max values in a file or should i change increment logic completely?

i appreciate any help

Related questions

Consistancy of pairs in python

3 answers

See also questions close to this topic