CODEWITHSUNDEEP
pythonstringperformance
ChipSkylark
ChipSkylark

Reputation: 75

Efficiently find repeated characters in a string

I know that the efficiency of this code is not optimal (esp. with gigantic inputs), and I know that there is a way to change this algorithm to handle other data types and not just a repetition in a string (obviously there are only so many characters to search through).

Is there any way I can increase efficiency here?

I tried using a dictionary and the function kept returning 'none' so I tried a list and things worked out fine.

Thanks ahead of time to anyone who can help me out!

def find_repeater(string):
    my_list = []
    my_list.append(string[0])

    for i in range (1, len(string)):

        if string[i] in my_list:
            print 'repetition found'
            return (string[i])

        else:
            my_list.append(string[i])

print find_repeater('abca')

now with a dictionary....(it keeps printing 'none' to the console)

def find_repeater(string):
    my_dict = {}
    my_dict[0] = string[0]

    for i in range (1, len(string)):

        if string[i] in my_dict:
            print 'repetition found'
            return string[i]

        else:
            my_dict[i] = string[i]

print find_repeater('abca')

Upvotes: 6

Views: 27071

Answers (7)

Arun Tom
Arun Tom

Reputation: 879

def rec_char(s):
    buf={}
    for c in s:
        try:
            print(buf[c],end=", ")
        except:
            buf[c]=c


rec_char("ABCAB")

This function in python3 with time complexity O(n) will print the characters that appear more than once.

Upvotes: 0

Hax0
Hax0

Reputation: 103

Another approach can be as simple as:

def repeting_count(text):

    working_text = str(text.lower())

    dup = []

    for char in working_text:
        if working_text.count(char) > 1:
            dup.append(char)

        else:
            pass

    for num in dup:
        while dup.count(num) > 1:
            dup.remove(num)

Upvotes: 0

georg
georg

Reputation: 214959

As this is a performance question, let's do some timings:

def test_set(xs):
    seen = set()  # O(1) lookups
    for x in xs:
        if x not in seen:
            seen.add(x)
        else:
            return x

import collections

def test_counter(xs):
    freq = collections.Counter(xs)
    for k in freq:
        if freq[k] > 1:
            return k

def test_dict(xs):
    d = {}
    for x in xs:
        if x in d:
            return x
        d[x] = 1

def test_sort(xs):
    ys = sorted(xs)

    for n in range(1, len(xs)):
        if ys[n] == ys[n-1]:
            return ys[n]

##

import sys, timeit
print (sys.version + "\n")
xs = list(range(10000)) + [999]
fns = [p for name, p in globals().items() if name.startswith('test')]
for fn in fns:
    assert fn(xs) == 999
    print ('%50s %.5f' % (fn, timeit.timeit(lambda: fn(xs), number=100)))

I'm testing on an list of integers rather than a string (because with a string you can't get more than 256 loops). The results on my machine look like this:

3.2.3 (v3.2.3:3d0686d90f55, Apr 10 2012, 11:25:50) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)]

                <function test_set at 0x1020f7380> 0.19265
               <function test_dict at 0x1020f7490> 0.12725
               <function test_sort at 0x1020f7518> 0.04683
            <function test_counter at 0x1020f7408> 0.92485

So the sort method appears to be the winner. I guess this is because it doesn't waste time creating hashes and allocating dict/set structures. Also, if you don't care about the source list being changed, you can do xs.sort() instead of ys = sorted(xs), which gives you zero memory footprint.

On the other side, if repeated items are more probable to occur towards the beginning of the input (as in xs = 'abcdef' * 10000), the set method will perform the best, as it, unlike sort or Counter, returns immediately once a repeat is found and doesn't need to preprocess the whole list. You should also use set if you need the first repeating element, not just one of them.

Counter is a nice tool, but it's not designed for performance, so if you really have to deal with "gigantic inputs", go with sets (if they fit in memory) or mergesort if they don't.

Upvotes: 15

amehta
amehta

Reputation: 1317

This should work.

def return_dupe(string):
    d = {}
    [d.update({k:2}) if k in d else d.update({k:1}) for k in string]
    return [key for key in d if d[key] > 1]

Upvotes: 0

Nir Alfasi
Nir Alfasi

Reputation: 53535

You can use collections to find repeating characters:

import collections

freq = collections.Counter("abcda")
for k in freq:
    if freq[k] > 1:
        print k # prints "a"
        break

If you want only to find if there are repetitions (without finding the repeated characters):

letters = list("abcda")
no_rep = set(letters)
print len(letters) > len(no_rep) # prints 'True' when there are repeating characters

Upvotes: 4

inspectorG4dget
inspectorG4dget

Reputation: 113975

def find_repeater(mystr):
    seen = set()  # O(1) lookups
    for char in mystr:
        if char not in seen:
            seen.add(char)
        else:
            print('repetition found')
            return char

Upvotes: 2

hd1
hd1

Reputation: 34667

Here you go, using a dictionary:

def find_repeater(string):
    my_list = {}
    my_list[string[0]] = 1
    for i in range (1, len(string)):
        if string[i] in my_list.keys():
            print 'repetition found'
            return (string[i])
        else:
            my_list[string[i]] = 1
print find_repeater('abca')

Personally, though, I would use a set here:

def find_repeater(string):
    my_list = set()
    my_list.add(string[0])
    for i in range (1, len(string)):
        if string[i] in my_list:
            print 'repetition found'
            return (string[i])
        else:
            my_list.add(string[i])
print find_repeater('abca')

Upvotes: 1

Related Questions