Hướng dẫn how do you find the count of the repeated letters in the string python? - làm thế nào để bạn tìm thấy số lượng các ký tự lặp lại trong chuỗi python?

Grand Performance Comparison

Scroll to the end for a TL;DR graph

Since I had "nothing better to do" (understand: I had just a lot of work), I decided to do a little performance contest. I assembled the most sensible or interesting answers and did some simple

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

>>> s = 'ZDXMZKMXFDKXZFKZ'
>>> len(s)
16

Be aware that results might vary for different inputs, be it different length of the string or different number of distinct characters, or different average number of occurrences per character.

Don't reinvent the wheel

Python has made it simple for us. The

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

taken from @oefe, nice find

>>> timeit('Counter(s)', globals=locals())
8.208566107001388

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

¿Dictionary, comprende?

Let's try using a simple

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

I came up with this myself...

>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002

This will go through

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

I came up with this myself, and so did @IrshadBhat

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

Better. But we still have to search through the string to count the occurrences. One search for each distinct character. That means we're going to read the string more than once. We can do better than that! But for that, we have to get off our declarativist high horse and descend into an imperative mindset.

Exceptional code

AKA Gotta catch 'em all!

inspired by @anthony

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

Well, it was worth a try. If you dig into the Python source (I can't say with certainty because I have never really done that), you will probably find that when you do

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

made by @anthony

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except:
...     d[c] = 1
... ''', globals=locals())
3.3506563019982423

It does save some time, so one might be tempted to use this as some sort of optimization.
Don't do that! Or actually do. Do it now:

INTERLUDE 1

import time
while True:
  try:
    time.sleep(1)
  except:
    print("You're trapped in your own trap!")

You see? It catches

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

INTERLUDE 2

import sys
try:
  print("Goodbye. I'm going to die soon.")
  sys.exit()
except:
  print('BACK FROM THE DEAD!!!')

Now back to counting letters and numbers and other characters.

Playing catch-up

Exceptions aren't the way to go. You have to try hard to catch up with them, and when you finally do, they just throw up on you and then raise their eyebrows like it's your fault. Luckily brave fellows have paved our way so we can do away with exceptions, at least in this little exercise.

The

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except:
...     d[c] = 1
... ''', globals=locals())
3.3506563019982423

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except:
...     d[c] = 1
... ''', globals=locals())
3.3506563019982423

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except:
...     d[c] = 1
... ''', globals=locals())
3.3506563019982423

credit goes to @Usman

>>> timeit('''
... d = {}
... for c in s:
...   d[c] = d.get(c, 0) + 1
... ''', globals=locals())
3.2133633289995487

Almost as fast as the set-based dict comprehension. On larger inputs, this one would probably be even faster.

Use the right tool for the job

For at least mildly knowledgeable Python programmer, the first thing that comes to mind is probably

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except:
...     d[c] = 1
... ''', globals=locals())
3.3506563019982423

hope @AlexMartelli won't crucify me for

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except:
...     d[c] = 1
... ''', globals=locals())
3.3506563019982423

>>> timeit('''
... dd = defaultdict(int)
... for c in s:
...   dd[c] += 1
... ''', globals=locals())
3.3430528169992613

Not that bad. I'd say the increase in execution time is a small tax to pay for the improved readability. However, we also favor performance, and we will not stop here. Let's take it further and prepopulate the dictionary with zeros. Then we won't have to check every time if the item is already there.

hats off to @sqram

>>> timeit('Counter(s)', globals=locals())
8.208566107001388

That's good. Over three times as fast as

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('Counter(s)', globals=locals())
8.208566107001388

Practicality beats purity (except when it's not really practical)

Now a bit different kind of counter. @IdanK has come up with something interesting. Instead of using a hash table (a.k.a. dictionary a.k.a.

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except:
...     d[c] = 1
... ''', globals=locals())
3.3506563019982423

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except:
...     d[c] = 1
... ''', globals=locals())
3.3506563019982423

import time
while True:
  try:
    time.sleep(1)
  except:
    print("You're trapped in your own trap!")

import time
while True:
  try:
    time.sleep(1)
  except:
    print("You're trapped in your own trap!")

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

Như một lưu ý phụ, kỹ thuật này được sử dụng trong thuật toán sắp xếp thời gian tuyến tính được gọi là sắp xếp đếm hoặc sắp xếp đếm. Nó rất hiệu quả, nhưng phạm vi của các giá trị được sắp xếp bị hạn chế, vì mỗi giá trị phải có bộ đếm riêng. Để sắp xếp một chuỗi các số nguyên 32 bit, sẽ cần 4,3 tỷ quầy.count sort or counting sort. It's very efficient, but the range of values being sorted is limited, since each value has to have its own counter. To sort a sequence of 32-bit integers, 4.3 billion counters would be needed.

>>> timeit('Counter(s)', globals=locals())
8.208566107001388

Ouch! Không mát mẻ! Hãy thử và xem mất bao lâu khi chúng ta bỏ qua việc xây dựng từ điển.

>>> timeit('Counter(s)', globals=locals())
8.208566107001388

Vẫn tệ. Nhưng chờ đã,

import time
while True:
  try:
    time.sleep(1)
  except:
    print("You're trapped in your own trap!")

import time
while True:
  try:
    time.sleep(1)
  except:
    print("You're trapped in your own trap!")

>>> timeit('Counter(s)', globals=locals())
8.208566107001388

Đáng chú ý. Bây giờ chúng ta hãy đặt từ điển trở lại.

>>> timeit('Counter(s)', globals=locals())
8.208566107001388

Chậm hơn gần sáu lần. Tại sao phải mất quá lâu? Bởi vì khi chúng tôi

import time
while True:
  try:
    time.sleep(1)
  except:
    print("You're trapped in your own trap!")

>>> timeit('Counter(s)', globals=locals())
8.208566107001388

Nó có thể sẽ không tốt hơn thế, ít nhất là không phải là một đầu vào nhỏ như vậy. Thêm vào đó, nó chỉ có thể sử dụng cho các ký tự EASCII 8 bit. О о

Và người chiến thắng là...

>>> timeit('Counter(s)', globals=locals())
8.208566107001388

Chuẩn rồi. Ngay cả khi bạn phải kiểm tra mỗi lần liệu

import time
while True:
  try:
    time.sleep(1)
  except:
    print("You're trapped in your own trap!")

import time
while True:
  try:
    time.sleep(1)
  except:
    print("You're trapped in your own trap!")

import time
while True:
  try:
    time.sleep(1)
  except:
    print("You're trapped in your own trap!")

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except:
...     d[c] = 1
... ''', globals=locals())
3.3506563019982423

Đó là tất cả mọi người

Bài tập nhỏ này dạy chúng ta một bài học: khi tối ưu hóa, luôn luôn đo lường hiệu suất, lý tưởng với các đầu vào dự kiến ​​của bạn. Tối ưu hóa cho trường hợp chung. Đừng cho rằng một cái gì đó thực sự hiệu quả hơn chỉ vì độ phức tạp tiệm cận của nó thấp hơn. Và cuối cùng nhưng không kém phần quan trọng, hãy tiếp tục đọc trong tâm trí. Cố gắng tìm một sự thỏa hiệp giữa "thân thiện với máy tính" và "thân thiện với con người".

CẬP NHẬT

Tôi đã được thông báo bởi @martijnpieters về hàm

import sys
try:
  print("Goodbye. I'm going to die soon.")
  sys.exit()
except:
  print('BACK FROM THE DEAD!!!')

import sys
try:
  print("Goodbye. I'm going to die soon.")
  sys.exit()
except:
  print('BACK FROM THE DEAD!!!')

>>> timeit('Counter(s)', globals=locals())
8.208566107001388

Chức năng này được thực hiện trong C, vì vậy nó sẽ nhanh hơn, nhưng hiệu suất bổ sung này có giá. Giá không tương thích với Python 2 và thậm chí có thể là phiên bản trong tương lai, vì chúng tôi đang sử dụng một chức năng riêng tư.

Từ tài liệu:

. Nó nên được coi là một chi tiết thực hiện và có thể thay đổi mà không cần thông báo trước.

Điều đó nói rằng, nếu bạn vẫn muốn tiết kiệm 620 nano giây đó cho mỗi lần lặp:

>>> timeit('Counter(s)', globals=locals())
8.208566107001388

Cập nhật 2: Chuỗi lớn

Tôi nghĩ rằng có thể là một ý tưởng tốt để chạy lại các thử nghiệm trên một số đầu vào lớn hơn, vì chuỗi 16 ký tự là một đầu vào nhỏ đến mức tất cả các giải pháp có thể khá nhanh (1.000 lần lặp trong vòng dưới 30 mili giây).

Tôi quyết định sử dụng các tác phẩm hoàn chỉnh của Shakespeare như một tập đoàn thử nghiệm, hóa ra là một thách thức khá (vì nó có kích thước trên 5mib). Tôi chỉ sử dụng 100.000 ký tự đầu tiên của nó và tôi phải giới hạn số lần lặp từ 1.000.000 đến 1.000.

>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002

Naiïve θ (n2) Từ điển thời gian hiểu đơn giản là không hoạt động

>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002

Thông minh θ (n) Từ điển thời gian hiểu được hoạt động tốt

>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002

Ngoại lệ là vụng về và chậm

>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002

Bỏ qua kiểm tra loại ngoại lệ không tiết kiệm thời gian (vì ngoại lệ chỉ được ném một vài lần)

>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002

import sys
try:
  print("Goodbye. I'm going to die soon.")
  sys.exit()
except:
  print('BACK FROM THE DEAD!!!')

>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002

import sys
try:
  print("Goodbye. I'm going to die soon.")
  sys.exit()
except:
  print('BACK FROM THE DEAD!!!')

>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002

import sys
try:
  print("Goodbye. I'm going to die soon.")
  sys.exit()
except:
  print('BACK FROM THE DEAD!!!')

>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002

Sử dụng

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except:
...     d[c] = 1
... ''', globals=locals())
3.3506563019982423

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('{c: s.count(c) for c in s}', globals=locals())
4.551155784000002

Để lại chuyển đổi cuối cùng thành

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

Không quan trọng bạn xây dựng

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except:
...     d[c] = 1
... ''', globals=locals())
3.3506563019982423

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

Nếu bạn chuyển đổi

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except:
...     d[c] = 1
... ''', globals=locals())
3.3506563019982423

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

Biến thể

>>> timeit('''
... d = {}
... for c in s:
...   d[c] = d.get(c, 0) + 1
... ''', globals=locals())
3.2133633289995487

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

import sys
try:
  print("Goodbye. I'm going to die soon.")
  sys.exit()
except:
  print('BACK FROM THE DEAD!!!')

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

>>> timeit('''
... d = {}
... for c in s:
...   d[c] = d.get(c, 0) + 1
... ''', globals=locals())
3.2133633289995487

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

Phán quyết cuối cùng: Sử dụng >>> timeit('{c: s.count(c) for c in set(s)}', globals=locals()) 3.1484066140001232 9 trừ khi bạn không thể hoặc không muốn :)

Phụ lục: Numpy

Gói

>>> timeit('''
... d = {}
... for c in s:
...   d[c] = d.get(c, 0) + 1
... ''', globals=locals())
3.2133633289995487

>>> timeit('''
... dd = defaultdict(int)
... for c in s:
...   dd[c] += 1
... ''', globals=locals())
3.3430528169992613

Cách thức hoạt động của phương thức này rất khác với tất cả các phương pháp trên:

• Trước tiên, nó sắp xếp một bản sao của đầu vào bằng QuickSort, đó là hoạt động thời gian O (N2) trong trường hợp xấu nhất, mặc dù O (N log n) trung bình và O (N) trong trường hợp tốt nhất.O(n2) time operation in the worst case, albeit O(n log n) on average and O(n) in the best case.

• Sau đó, nó tạo ra một mảng "mặt nạ" chứa

  >>> timeit('''
  ... dd = defaultdict(int)
  ... for c in s:
  ...   dd[c] += 1
  ... ''', globals=locals())
  3.3430528169992613
  

  1 tại các chỉ số nơi việc chạy cùng một giá trị bắt đầu, viz. tại các chỉ số nơi giá trị khác với giá trị trước đó. Các giá trị lặp đi lặp lại tạo ra

  >>> timeit('''
  ... dd = defaultdict(int)
  ... for c in s:
  ...   dd[c] += 1
  ... ''', globals=locals())
  3.3430528169992613
  

  2 trong mặt nạ. Ví dụ:

  >>> timeit('''
  ... dd = defaultdict(int)
  ... for c in s:
  ...   dd[c] += 1
  ... ''', globals=locals())
  3.3430528169992613
  

  3 tạo ra mặt nạ

  >>> timeit('''
  ... dd = defaultdict(int)
  ... for c in s:
  ...   dd[c] += 1
  ... ''', globals=locals())
  3.3430528169992613
  

  4.

• Mặt nạ này sau đó được sử dụng để trích xuất các giá trị duy nhất từ ​​đầu vào được sắp xếp -

  >>> timeit('''
  ... dd = defaultdict(int)
  ... for c in s:
  ...   dd[c] += 1
  ... ''', globals=locals())
  3.3430528169992613
  

  5 trong mã bên dưới. Trong ví dụ của chúng tôi, chúng sẽ là

  >>> timeit('''
  ... dd = defaultdict(int)
  ... for c in s:
  ...   dd[c] += 1
  ... ''', globals=locals())
  3.3430528169992613
  

  6.

• Các vị trí của các giá trị

  >>> timeit('''
  ... dd = defaultdict(int)
  ... for c in s:
  ...   dd[c] += 1
  ... ''', globals=locals())
  3.3430528169992613
  

  1 trong mặt nạ được đưa vào một mảng và độ dài của đầu vào được nối ở cuối mảng này. Đối với ví dụ trên, mảng này sẽ là

  >>> timeit('''
  ... dd = defaultdict(int)
  ... for c in s:
  ...   dd[c] += 1
  ... ''', globals=locals())
  3.3430528169992613
  

  8.

• Đối với mảng này, sự khác biệt giữa các yếu tố của nó được tính toán, ví dụ.

  >>> timeit('''
  ... dd = defaultdict(int)
  ... for c in s:
  ...   dd[c] += 1
  ... ''', globals=locals())
  3.3430528169992613
  

  9. Đây là các số lượng tương ứng của các phần tử trong mảng được sắp xếp -

  >>> timeit('Counter(s)', globals=locals())
  8.208566107001388
  

  00 trong mã bên dưới.

• Cuối cùng, chúng tôi tạo ra một từ điển bằng cách zipping

  >>> timeit('''
  ... dd = defaultdict(int)
  ... for c in s:
  ...   dd[c] += 1
  ... ''', globals=locals())
  3.3430528169992613
  

  5 và

  >>> timeit('Counter(s)', globals=locals())
  8.208566107001388
  

  00:

  >>> timeit('Counter(s)', globals=locals())
  8.208566107001388
  

  03.

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

Đối với đầu vào thử nghiệm (100.000 ký tự đầu tiên của các tác phẩm hoàn chỉnh của Shakespeare), phương pháp này thực hiện tốt hơn bất kỳ thử nghiệm nào khác ở đây. Nhưng lưu ý rằng trên một đầu vào khác, phương pháp này có thể mang lại hiệu suất tồi tệ hơn các phương pháp khác. Độ sắp xếp trước của đầu vào và số lần lặp lại trên mỗi yếu tố là các yếu tố quan trọng ảnh hưởng đến hiệu suất.

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

Nếu bạn đang nghĩ về việc sử dụng phương pháp này vì nó nhanh gấp đôi so với

>>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
3.1484066140001232

• >>> timeit('{c: s.count(c) for c in set(s)}', globals=locals())
  3.1484066140001232
  

  9 có độ phức tạp thời gian tuyến tính.

  >>> timeit('''
  ... dd = defaultdict(int)
  ... for c in s:
  ...   dd[c] += 1
  ... ''', globals=locals())
  3.3430528169992613
  

  0 là tuyến tính tốt nhất, bậc hai tồi tệ nhất.

• Tăng tốc không thực sự đáng kể - bạn tiết kiệm ~ 3,5 mili giây mỗi lần lặp trên đầu vào có độ dài 100.000.

• Sử dụng

  >>> timeit('''
  ... dd = defaultdict(int)
  ... for c in s:
  ...   dd[c] += 1
  ... ''', globals=locals())
  3.3430528169992613
  

  0 rõ ràng yêu cầu

  >>> timeit('''
  ... d = {}
  ... for c in s:
  ...   d[c] = d.get(c, 0) + 1
  ... ''', globals=locals())
  3.2133633289995487
  

  9.

Điều đó được xem xét, có vẻ hợp lý khi sử dụng

>>> timeit('''
... d = {}
... for c in s:
...   try:
...     d[c] += 1
...   except KeyError:
...     d[c] = 1
... ''', globals=locals())
3.7060273620008957

>>> timeit('''
... d = {}
... for c in s:
...   d[c] = d.get(c, 0) + 1
... ''', globals=locals())
3.2133633289995487

Phụ lục 2: Một cốt truyện có phần hữu ích

Tôi đã chạy 13 phương pháp khác nhau ở trên trên các tiền tố của các tác phẩm hoàn chỉnh của Shakespeare và tạo ra một cốt truyện tương tác. Lưu ý rằng trong sơ đồ, cả tiền tố và thời lượng được hiển thị theo thang đo logarit (các tiền tố được sử dụng có độ dài tăng theo cấp số nhân). Nhấp vào các mục trong truyền thuyết để hiển thị/ẩn chúng trong cốt truyện.

Bấm để mở!

Làm thế nào để bạn đếm số lượng chữ cái lặp lại trong một chuỗi trong Python?

Làm cách nào để đếm số lượng ký tự lặp lại trong một chuỗi?

Làm thế nào để bạn đếm cùng một chữ cái trong Python?