[Python] Match beginning of two strings

[Python] Match beginning of two strings

	Ravi
	Aug 3, 2003 at 3:14 am

Are you trying to match any to any strings? or only a pair as above?

Just a pair at a time, and I only want the first N characters that are
common to both strings. The os.path.commonprefix works nicely. Thanks
for your help.

Ravi

Search Discussions

Discussion Posts

Ravi: Certainly not where I was expecting it, Thanks Ravi

Follow ups

John Machin: I don't think that os.path.commonprefix was designed with 200Gb of data in mind. Inspection of Lib/*path.py gives one the impression that it spends a lot of time discovering that the first element is a prefix of itself. Ravi, You may need to drop down to C to get the speed you want for your requirement to find the longest common prefix of two strings. Two things puzzling me: (1) how you would do this with regular expressions (2) you have 200Gb now, new data arriving at the rate of 1Gb per hour,
Jeff Epler: This is a naive implementation of the 'extract' function. def extract(a, b): m = min(len(a), len(b)) for i in range(m): if a[i] != b[i]: return a[:i] return a[:m] Here's one that uses the new zip() function: def extract2(a, b): m = min(len(a), len(b)) for i, ai, bi in (range(m), a, b): if ai != bi: return a[:i] return a[:m] .. unfortunately, it seems to be slower than the first method. On my machine (800MHz PIII): $ python timeit.py -s 'import ravi' \
Ravi: Well, I timed os.path.commonprefix with some typical data and it's pulling about 40usec per loop. So I did what I hated and coded a little function in C. Goes something like this. My reasoning is that usually the point where the strings start to differ is in the 30 - 50 character range. Basically the idea is the same as a binary search on a sorted array. Divide and conquer by going halfway each time. Read in both strings. Check to see if the first character matches. If yes: Check halfway

Related Discussions

Discussion Navigation

view	thread \| post
posts	‹ prev \| 4 of 27 \| next ›

Discussion Overview

group	python-list @
categories	python
posted	Aug 2, '03 at 9:39p
active	Aug 22, '03 at 7:42a
posts	27
users	12
website	python.org

font	variable	Hotkey: f
user style	avatars	Hotkey: a

[Python] Match beginning of two strings

Search Discussions

Discussion Posts

Related Discussions

12 users in discussion