Проверка, являются ли две строки перестановками друг друга в Python

Question

Я проверяю, являются ли две строки a и b перестановками друг друга, и мне интересно, каков идеальный способ сделать это в Python. Из дзен Python: «Должен быть один - и желательно только один - очевидный способ сделать это», но я вижу, что есть как минимум два способа:

sorted(a) == sorted(b)

и

all(a.count(char) == b.count(char) for char in a)

но первый медленнее, когда (например) первый символ a нигде не находится в b, а второй медленнее, когда они на самом деле являются перестановками.

Есть ли лучший (или в смысле более Pythonic, или в смысле более быстрый в среднем) способ сделать это? Или я должен просто выбрать один из этих двух, в зависимости от того, какая ситуация, по моему мнению, наиболее распространена?

Answer 1

Вот способ O (n), который асимптотически лучше двух предложенных вами.

import collections

def same_permutation(a, b):
    d = collections.defaultdict(int)
    for x in a:
        d[x] += 1
    for x in b:
        d[x] -= 1
    return not any(d.itervalues())

## same_permutation([1,2,3],[2,3,1])
#. True

## same_permutation([1,2,3],[2,3,1,1])
#. False

Answer 2

"но первый медленнее, когда (например) первый символ a нигде не находится в b".

Этот вид анализа производительности вырожденного случая не очень хорошая идея. Это пустая трата потерянного времени на размышления над всевозможными неясными случаями.

Выполните только «общий» анализ в стиле O .

В целом, сортировки: O ( n log ( n )).

Решение a.count(char) for char in a: O ( n ² ). Каждый проход отсчета - это полная проверка строки.

Если какой-то непонятный особый случай оказывается быстрее или медленнее, это, возможно, интересно. Но это имеет значение только тогда, когда вы знаете частоту ваших неясных особых случаев. При анализе алгоритмов сортировки важно отметить, что значительное количество сортировок включает в себя данные, которые уже находятся в правильном порядке (либо по счастливой случайности, либо благодаря продуманному замыслу), поэтому производительность сортировки по предварительно отсортированным данным имеет значение.

В вашем неясном особом случае («первый символ a нигде в b») это достаточно часто, чтобы иметь значение? Если это просто особый случай, о котором вы подумали, отложите его в сторону. Если это факт о ваших данных, то подумайте.

Answer 3

эвристически, вероятно, вам лучше разделить их по размеру строки.

псевдокод:

returnvalue = false
if len(a) == len(b)
   if len(a) < threshold
      returnvalue = (sorted(a) == sorted(b))
   else
       returnvalue = naminsmethod(a, b)
return returnvalue

Если производительность критична, а размер строки может быть большим или маленьким, то это то, что я бы сделал.

Довольно часто делить подобные вещи по размеру или типу ввода. Алгоритмы имеют разные сильные или слабые стороны, и было бы глупо использовать один, где другой был бы лучше ... В этом случае метод Намина является O (n), но имеет больший постоянный коэффициент, чем метод сортировки O (n log n).

Answer 4

Я думаю, что первый - это «очевидный» путь. Он короче, понятнее и, скорее всего, быстрее во многих случаях, потому что встроенная сортировка Python высоко оптимизирована.

Answer 5

Ваш второй пример на самом деле не сработает:

all(a.count(char) == b.count(char) for char in a)

будет работать, только если b не содержит лишних символов, кроме a. Он также выполняет дублирующую работу, если символы в строке повторяются.

Если вы хотите узнать, являются ли две строки перестановками одинаковых уникальных символов, просто выполните:

set(a) == set(b)

Чтобы исправить ваш второй пример:

all(str1.count(char) == str2.count(char) for char in set(a) | set(b))

Объекты set () перегружают побитовый оператор ИЛИ, чтобы он вычислялся как объединение обоих наборов. Это обеспечит зацикливание всех символов обеих строк только для каждого символа.

Тем не менее, метод sorted () намного проще и интуитивнее, и я бы использовал его.

Answer 6

Вот несколько временных вычислений для очень маленьких строк с использованием двух разных методов:
1. сортировка
2. подсчет (в частности, оригинальный метод @namin).

a, b, c = 'confused', 'unfocused', 'foncused'

sort_method = lambda x,y: sorted(x) == sorted(y)

def count_method(a, b):
    d = {}
    for x in a:
        d[x] = d.get(x, 0) + 1
    for x in b:
        d[x] = d.get(x, 0) - 1
    for v in d.itervalues():
        if v != 0:
            return False
    return True

Среднее время выполнения 2 методов на 100 000 циклов:

несоответствие (строка a и b)

$ python -m timeit -s 'import temp' 'temp.sort_method(temp.a, temp.b)'
100000 loops, best of 3: 9.72 usec per loop
$ python -m timeit -s 'import temp' 'temp.count_method(temp.a, temp.b)'
10000 loops, best of 3: 28.1 usec per loop

совпадение (строка a и c)

$ python -m timeit -s 'import temp' 'temp.sort_method(temp.a, temp.c)'
100000 loops, best of 3: 9.47 usec per loop
$ python -m timeit -s 'import temp' 'temp.count_method(temp.a, temp.c)'
100000 loops, best of 3: 24.6 usec per loop

Имейте в виду, что используемые строки очень маленькие. Временная сложность методов различна, поэтому вы увидите разные результаты с очень большими строками. Выберите в соответствии с вашими данными, вы даже можете использовать комбинацию из двух.

Answer 7

Извините, что мой код не на Python, я никогда не использовал его, но я уверен, что это легко можно перевести на Python. Я считаю, что это быстрее, чем все другие примеры, уже опубликованные. Это также O (n), но останавливается как можно скорее:

public boolean isPermutation(String a, String b) {
    if (a.length() != b.length()) {
        return false;
    }

    int[] charCount = new int[256];
    for (int i = 0; i < a.length(); ++i) {
        ++charCount[a.charAt(i)];
    }

    for (int i = 0; i < b.length(); ++i) {
        if (--charCount[b.charAt(i)] < 0) {
            return false;
        }
    }
    return true;
}

Сначала я использую не словарь, а массив размером 256 для всех символов. Доступ к индексу должен быть намного быстрее. Затем, когда вторая строка повторяется, я немедленно возвращаю false, когда счетчик становится меньше 0. Когда второй цикл завершится, вы можете быть уверены, что строки являются перестановками, потому что строки имеют одинаковую длину и символы не использовались чаще в б по сравнению с.

Answer 8

Я провел довольно тщательное сравнение на Java со всеми словами в моей книге. Метод подсчета превосходит метод сортировки во всех отношениях. Результаты:

Testing against 9227 words.

Permutation testing by sorting ... done.        18.582 s
Permutation testing by counting ... done.       14.949 s

Если кому-то нужен алгоритм и набор тестовых данных, оставьте комментарий.

Answer 9

Во-первых, для решения таких проблем, например, Если строка 1 и строка 2 в точности совпадают или нет, вы можете легко использовать «если», так как это O (1). Во-вторых, важно учитывать, что, являются ли они только числовыми значениями или они также могут быть словами в строке. Если последнее верно (слова и числовые значения находятся в строке одновременно), ваше первое решение не будет работать. Вы можете улучшить его, используя функцию "ord ()", чтобы сделать его числовым значением ASCII. Однако, в конце концов, вы используете сортировку; следовательно, в худшем случае ваша временная сложность будет O (NlogN). На этот раз сложность не плохая. Но вы можете сделать лучше. Вы можете сделать это O (N). Мое «предложение» использует Array (список) и устанавливается одновременно. Обратите внимание, что для нахождения значения в массиве требуется итерация, поэтому сложность по времени равна O (N), но при поиске значения в наборе (которое, я думаю, реализовано с помощью HashTable в Python, я не уверен) имеет O (1) сложность по времени :

def Permutation2(Str1, Str2):

ArrStr1 = list(Str1) #convert Str1 to array
SetStr2 = set(Str2) #convert Str2 to set

ArrExtra = []

if len(Str1) != len(Str2): #check their length
    return False

elif Str1 == Str2: #check their values
    return True

for x in xrange(len(ArrStr1)):
    ArrExtra.append(ArrStr1[x])

for x in xrange(len(ArrExtra)): #of course len(ArrExtra) == len(ArrStr1) ==len(ArrStr2)
    if ArrExtra[x] in SetStr2: #checking in set is O(1)
        continue
    else:
        return False

return True

Answer 10

Пойдите с первым - это намного проще и понятнее. Если вы на самом деле имеете дело с невероятно большими строками и производительность является реальной проблемой, то не используйте Python, используйте что-то вроде C.

Что касается дзен Python, то должен быть только один очевидный способ сделать что-то, относящееся к маленьким, простым вещам. Очевидно, что для любой достаточно сложной задачи всегда найдутся миллионы небольших вариаций способов ее решения.