Как найти индекс числа в матрице

This is a benchmark of all the answers posted so far including two of my own. I think you may find the results useful, enlightening, and maybe even surprising. ;¬)

Note I’ve put the target value to middle of matrix to simulate its average location if the data are random in an effort to level the playing field (a little bit) for algorithms that stop as soon it’s is found — the comparison still isn’t really fair, however.

Runs under both Python 2 & 3.

Update — Added answers that have been posted after last update to this one.

from __future__ import print_function
import numpy as np
import sys
from textwrap import dedent
import timeit

EXECUTIONS = 1000000  # Number of times each algorithm is executed per timing run.
TIMINGS = 3  # Number of timing runs.

SETUP = dedent("""
    # Make accessible in algorithms.
    from __main__ import np
    mymatrix=[[1,2,3], [4,9,6], [7,8,5]]  # Target value in middle.
    val = 9  # Target value.
""")

algorithms = {
    "user2459905 (OP) - all occurrences": dedent("""
        # finds all occurrences
        found = []
        for i,j in enumerate(mymatrix):
           for k,l in enumerate(j):
             if l==val:
                 found.append((i,k))
    """),

    "ayush thakur (fixed) - all occurrences": dedent("""
        # finds all occurrences
        found = []
        for i, e in enumerate(mymatrix):
            for j, ee in enumerate(e):
                if val == ee:  # Fixed.
                    found.append((i, j))
    """),


    "martineau #1 - all occurrences": dedent("""
        # finds all occurrences
        width = len(mymatrix[0])
        found = []
        posn = 0
        for row in mymatrix:
            if val not in row:
                posn += width
            else:
                for col in row:
                    if col == val:
                        found.append((posn // width, posn % width))
                    posn += 1
    """),

    "martineau #2 - all occurrences": dedent("""
        # finds all occurrences
        width = len(mymatrix[0])
        found = []
        posn = 0
        for row in mymatrix:
            if val in row:
                for y,col in enumerate(row):
                    if col == val:
                        found.append((posn // width, y))
            posn += width
    """),

    "mmtauqir - first occurrence": dedent("""
        # finds all occurrences
        matrix_dim = len(mymatrix[0])
        item_index = 0
        for row in mymatrix:
            for i in row:
                if i == val:
                    break
                item_index += 1
            if i == val:
                break
        found = (int(item_index / matrix_dim), item_index % matrix_dim)
    """),

    "rtrwalker - all occurrences using numpy": dedent("""
        # finds all occurrences using numpy
        a = np.array(mymatrix)  # Convert mymatrix to a numpy array.
        found = np.where(a==val)
    """),

    "Ryan Haining - first occurrence (per row)": dedent("""
        # finds first occurrence in each row
        found = [(index, row.index(val)) for index, row in enumerate(mymatrix)
                                            if val in row]
    """),

}


# Benchmark algorithms
timings = [
        (label, min(timeit.repeat(algorithms[label], setup=SETUP,
                                  repeat=TIMINGS, number=EXECUTIONS)))
            for label in algorithms
    ]

# Display metrics.
longest = max(len(timing[0]) for timing in timings)  # Length of longest label.

print('Fastest to slowest execution speeds with {}-bit Python {}.{}.{}'.format(
        64 if sys.maxsize > 2**32 else 32, *sys.version_info[:3]))
print('  with numpy version {}'.format(np.version.full_version),
      '-> {:,d} executions, best of {:,d})'.format(EXECUTIONS, TIMINGS))
print()

ranked = sorted(timings, key=lambda t: t[1])  # sort by speed (fastest first)
for timing in ranked:
    print("{:>{width}} : {:.6f} secs, rel speed {rel:6.3f}x".format(
          timing[0], timing[1], rel=timing[1]/ranked[0][1], width=longest))

Results:

Fastest to slowest execution speeds with 32-bit Python 2.7.18
  with numpy version 1.16.6 -> 1,000,000 executions, best of 3)

              mmtauqir - first occurrence : 0.667560 secs, rel speed  1.000x
Ryan Haining - first occurrence (per row) : 0.694786 secs, rel speed  1.041x
           martineau #1 - all occurrences : 0.752011 secs, rel speed  1.127x
           martineau #2 - all occurrences : 0.929674 secs, rel speed  1.393x
   ayush thakur (fixed) - all occurrences : 1.541785 secs, rel speed  2.310x
       user2459905 (OP) - all occurrences : 1.544341 secs, rel speed  2.313x
  rtrwalker - all occurrences using numpy : 3.334727 secs, rel speed  4.995x


Fastest to slowest execution speeds with 32-bit Python 3.8.8
  with numpy version 1.21.1 -> 1,000,000 executions, best of 3)

              mmtauqir - first occurrence : 0.734707 secs, rel speed  1.000x
Ryan Haining - first occurrence (per row) : 0.749999 secs, rel speed  1.021x
           martineau #2 - all occurrences : 0.820354 secs, rel speed  1.117x
           martineau #1 - all occurrences : 0.880883 secs, rel speed  1.199x
       user2459905 (OP) - all occurrences : 1.436644 secs, rel speed  1.955x
   ayush thakur (fixed) - all occurrences : 1.638413 secs, rel speed  2.230x
  rtrwalker - all occurrences using numpy : 5.713464 secs, rel speed  7.777x

You can also add a tag to your function to search the occurrences of your input matrix/list.

For example:

If you input is 1D vector:

def get_index_1d(a = [], val = 0, occurrence_pos = False):
    if not occurrence_pos:
        for k in range(len(a)):
            if a[k] == val:
                return k
    else:
        return [k for k in range(len(a)) if a[k] == val]

Output:

a = [1,10,54,85, 10]
index = get_index_1d(a, 10, False)
print("Without occurrence: ", index)
index = get_index_1d(a, 10, True)
print("With occurrence: ", index)

>>> Without occurrence:  1
>>> With occurrence:  [1, 4]

For 2D vector:

def get_index_2d(a = [], val = 0, occurrence_pos = False):
    if not occurrence_pos:
        for k in range(len(a)):
            for j in range(len(a[k])):
                if a[k][j] == val:
                    return (k, j)

    else:
        return [(k, j) for k in range(len(a)) for j in range(len(a[k])) if a[k][j] == val]

Output:

b = [[1,2],[3,4],[5,6], [3,7]]
index = get_index_2d(b, 3, False)
print("Without occurrence: ", index)
index = get_index_2d(b, 3, True)
print("With occurrence: ", index)

>>> Without occurrence:  (1, 0)
>>> With occurrence:  [(1, 0), (3, 0)]

Задача следующая: дана матрица $%A$% размера $%n times n$% с элементами $%a_{ij}$% из множества $%{ 0, 1 }$%. Известно, что существует единственное число $%k$%, такое, что $%a_{kj} = 0$% для всех $%j = 1, 2, dots, n$%, а также $%a_{ik} = 1$% для всех $%i = 1, 2, dots, k — 1, k + 1, dots, n$%. Требуется найти это число $%k$%, сделав порядка $%mathcal{O}(n)$% операций.

Заметил следующее: для $%i neq j$% имеем $$a_{ij} = 0 Rightarrow j neq r quad text{и} quad a_{ij} = 1 Rightarrow i neq r .$$

Как из этого наблюдения построить алгоритм с подходящим временем работы $%mathcal{O}(n)$%?

Вроде бы можно, проверяя в некоторой последовательности значения $%a_{ij}$%, отсеивать, чему точно не может быть равно $%k$%, но как устроить обход $%a_{ij}$%, чтобы удовлетворить ограничению по времени?

myList=[1,10,54,85]
myList.index(54)

4 ответа

Лучший ответ

def find(element, matrix):
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == element:
                return (i, j)

def findall(element, matrix):
    result = []
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == element:
                result.append((i, j))
    return result

A = [[5, 10],
     [15, 20],
     [25, 5]]


find(25, A) # Will return (2, 0)
find(50, A) # Will return None

findall(5, A) # Will return [(0, 0), (2, 1)]
findall(4, A) # Will return []

myList=[1,10,54,85]
myvar = myList[0] # note that you access the first element with index 0

multi = [[0, 1, 2],
         [3, 4, 5],
         [6, 7, 8]
        ]

myvar = multi[1][2]

def find(element, matrix):
    for i, matrix_i in enumerate(matrix):
        for j, value in enumerate(matrix_i):
            if value == element:
                return (i, j)

def get_index_1d(a = [], val = 0, occurrence_pos = False):
    if not occurrence_pos:
        for k in range(len(a)):
            if a[k] == val:
                return k
    else:
        return [k for k in range(len(a)) if a[k] == val]

a = [1,10,54,85, 10]
index = get_index_1d(a, 10, False)
print("Without occurrence: ", index)
index = get_index_1d(a, 10, True)
print("With occurrence: ", index)

>>> Without occurrence:  1
>>> With occurrence:  [1, 4]

def get_index_2d(a = [], val = 0, occurrence_pos = False):
    if not occurrence_pos:
        for k in range(len(a)):
            for j in range(len(a[k])):
                if a[k][j] == val:
                    return (k, j)

    else:
        return [(k, j) for k in range(len(a)) for j in range(len(a[k])) if a[k][j] == val]

b = [[1,2],[3,4],[5,6], [3,7]]
index = get_index_2d(b, 3, False)
print("Without occurrence: ", index)
index = get_index_2d(b, 3, True)
print("With occurrence: ", index)

>>> Without occurrence:  (1, 0)
>>> With occurrence:  [(1, 0), (3, 0)]