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

Это - функция PHP, которую я записал приблизительно неделю назад, который проверяет, являются ли два слова анаграммами. Как это выдержало бы сравнение (если реализовано то же в Python) к другим предложенным методам? Комментарии?

public function is_anagram($word1, $word2) {
    $letters1 = str_split($word1);
    $letters2 = str_split($word2);
    if (count($letters1) == count($letters2)) {
        foreach ($letters1 as $letter) {
            $index = array_search($letter, $letters2);
            if ($index !== false) {
                unset($letters2[$index]);
            }
            else { return false; }
        }
        return true;
    }
    return false;        
}

Вот литерал перевод в Python версии PHP (JFS):

def is_anagram(word1, word2):
    letters2 = list(word2)
    if len(word1) == len(word2):
       for letter in word1:
           try:
               del letters2[letters2.index(letter)]
           except ValueError:
               return False               
       return True
    return False

Комментарии:

    1. The algorithm is O(N**2). Compare it to @namin's version (it is O(N)).
    2. The multiple returns in the function look horrible.

Эта версия быстрее, чем какие-либо примеры, представленные до сих пор кроме нее, на 20% медленнее, чем sorted(x) == sorted(y) для коротких строк. Это зависит от вариантов использования, но обычно 20%-е увеличение производительности недостаточно для выравнивания по ширине сложности кода при помощи другой версии для коротких и длинных строк (как в ответе @patros).

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

def isanagram(iterable1, iterable2):
    d = {}
    get = d.get
    for c in iterable1:
        d[c] = get(c, 0) + 1
    try:
        for c in iterable2:
            d[c] -= 1
        return not any(d.itervalues())
    except KeyError:
        return False

неясно, почему эта версия быстрее затем defaultdict одна (@namin) для большого iterable1 (протестированный на тезаурусе 25 МБ).

, Если мы заменяем get в цикле try: ... except KeyError затем, он работает в 2 раза медленнее для коротких строк т.е. когда существует немного дубликатов.

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

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

Я сделал довольно полное сравнение в Java со всеми словами в книге, которую я имел. Метод подсчета бьет метод сортировки каждым способом. Результаты:

Testing against 9227 words.

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

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

Извините, что мой код не находится в 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. Когда второй цикл закончился, можно быть уверены, что строки являются перестановкой, потому что строки имеют равную длину, и никакой символ не использовался чаще в b по сравнению с a.

Вот некоторое синхронизированное выполнение на очень маленьких строках, с помощью двух различных методов:
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

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

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

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))

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

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

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

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

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

Только делают , O - разрабатывает "полный" анализ.

В целом, виды O ( журнал n ( n)).

a.count(char) for char in a решение O ( <глоток> n 2 ). Каждая передача количества является полным исследованием строки.

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

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

Вот код martinus в Python. Это только работает на строки ASCII:

def is_permutation(a, b):
    if len(a) != len(b):
        return False

    char_count = [0] * 256
    for c in a:
        char_count[ord(c)] += 1

    for c in b:
        char_count[ord(c)] -= 1
        if char_count[ord(c)] < 0:
            return False

    return True

Вот путь, который является 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

В Python 3.1 / 2.7 вы можете просто использовать collections.Counter (a) == collections.Counter (b) .

Но sorted (a) == sorted (b) по-прежнему является наиболее очевидным ИМХО. Вы говорите о перестановках - изменении порядка - поэтому сортировка - очевидная операция по стиранию этого различия.