D********g
发帖数: 30 | 1 用C++写个函数，实现一个从一个长字符串里面找到一组子字符串的功能，但是不是一
般的子串，长字符串是一串由","分隔开的数字，比如"12,34,-54,65,367,-123,-9,68,
"， 然后我的函数的signature是：
string extractPartialString(const string& whole, int start, int end);
就是要找到在[start, end)之间的数字组成的子串。比如extractPartialString(input
, 2, 5)应该返回子串"-54,65,367"。我就是直接一个一个的按照分隔符","来找，找到
指定个数以后就返回，但是这样如果start很靠后的话会需要很长时间，毕竟要O(L+M)
的时间。不知道有没有什么更优化的算法可以实现这样的功能？请各位大牛支招，多谢！
以下是我目前的实现代码：
#include
#include
using namespace std;
/**
* Extract the partial string delimited by ',' from a whole string (must be
ended by ',')
* start: the start index of item (inclusive)
* end: the end index of item (exclusive)
*/
string extractPartialString(const string& whole, int start, int end)
{
int numItems = end - start;
size_t posCurrent = 0, posNext, length;
string elementStr, partialString;
int index = 0;
while ((posNext = whole.find(',', posCurrent)) != string::npos) {
length = posNext - posCurrent;
elementStr = whole.substr(posCurrent, length);
if (index >= start && index < end) {
partialString += elementStr + ",";
} else if (index >= end) {
break;
}
index++;
posCurrent = posNext + 1;
}
//remove the last delimiter to make it perfect
try {
partialString.erase(partialString.size() - 1, 1);
} catch (std::out_of_range & e) {
cerr << "Out of range exception: " << e.what() << endl;
}
return partialString;
}
int main()
{
string input = "12,34,-54,65,367,-123,-9,68,";
string output = extractPartialString(input, 2, 5);
cout << "Output partial string: " << output << endl;
} | q*c
发帖数: 9453 | 2 index comma location and u will get const time speed.
68,
input
谢！
【在 D********g 的大作中提到】
: 用C++写个函数，实现一个从一个长字符串里面找到一组子字符串的功能，但是不是一
: 般的子串，长字符串是一串由","分隔开的数字，比如"12,34,-54,65,367,-123,-9,68,
: "， 然后我的函数的signature是：
: string extractPartialString(const string& whole, int start, int end);
: 就是要找到在[start, end)之间的数字组成的子串。比如extractPartialString(input
: , 2, 5)应该返回子串"-54,65,367"。我就是直接一个一个的按照分隔符","来找，找到
: 指定个数以后就返回，但是这样如果start很靠后的话会需要很长时间，毕竟要O(L+M)
: 的时间。不知道有没有什么更优化的算法可以实现这样的功能？请各位大牛支招，多谢！
: 以下是我目前的实现代码：
: #include
| D********g
发帖数: 30 | 3 但是本身index comma位置的话就要O(N)了吧
【在 q*c 的大作中提到】
: index comma location and u will get const time speed.
:
: 68,
: input
: 谢！
| b***i
发帖数: 3043 | 4 这个串开始时哪里来的？总有个开始吧？
【在 D********g 的大作中提到】
: 但是本身index comma位置的话就要O(N)了吧
| D********g
发帖数: 30 | 5 就是一般的字符串，没有什么特别的，所以我想有没有什么更优化的算法来解决。
【在 b***i 的大作中提到】
: 这个串开始时哪里来的？总有个开始吧？
| p*****2
发帖数: 21240 | 6 感觉不行
上边说的是预处理
你要不重复用不行
【在 D********g 的大作中提到】
: 就是一般的字符串，没有什么特别的，所以我想有没有什么更优化的算法来解决。
| k**********g
发帖数: 989 | 7 逃不掉 O(N) 的工作量，但可以完美并发，把字串分为 1 mbytes 的小份，每一份发给
一个 worker thread / computer 点数分号，最後选出目标所在的小份再做一次顺序搜
索。 | D********g
发帖数: 30 | 8 这个是不是有点overkill了？如果万一start到end落在几个不同的小份上，最后还要连
起来，那还不如我的原始解，最差才O(N)，一般就是O(L+M)。而你这个至少需要O(N)
【在 k**********g 的大作中提到】
: 逃不掉 O(N) 的工作量，但可以完美并发，把字串分为 1 mbytes 的小份，每一份发给
: 一个 worker thread / computer 点数分号，最後选出目标所在的小份再做一次顺序搜
: 索。
| g*****g
发帖数: 34805 | 9 当你的字串terabyte级别的时候可以考虑那么做。
【在 D********g 的大作中提到】
: 这个是不是有点overkill了？如果万一start到end落在几个不同的小份上，最后还要连
: 起来，那还不如我的原始解，最差才O(N)，一般就是O(L+M)。而你这个至少需要O(N)
| p*****2
发帖数: 21240 | 10 terabytes memory也放不下呀
是完全不同的问题了
【在 g*****g 的大作中提到】
: 当你的字串terabyte级别的时候可以考虑那么做。
| | | g*****g
发帖数: 34805 | 11 不需要内存能放下。
【在 p*****2 的大作中提到】
: terabytes memory也放不下呀
: 是完全不同的问题了
| p*****2
发帖数: 21240 | 12 lz的问题应该是在memory里的
【在 g*****g 的大作中提到】
: 不需要内存能放下。
| N******K
发帖数: 10202 | 13 你整这个干啥
try {
partialString.erase(partialString.size() - 1, 1);
} catch (std::out_of_range & e) {
cerr << "Out of range exception: " << e.what() << endl;
}
判断一下partialString.size()不就行了
68,
input
谢！
【在 D********g 的大作中提到】
: 用C++写个函数，实现一个从一个长字符串里面找到一组子字符串的功能，但是不是一
: 般的子串，长字符串是一串由","分隔开的数字，比如"12,34,-54,65,367,-123,-9,68,
: "， 然后我的函数的signature是：
: string extractPartialString(const string& whole, int start, int end);
: 就是要找到在[start, end)之间的数字组成的子串。比如extractPartialString(input
: , 2, 5)应该返回子串"-54,65,367"。我就是直接一个一个的按照分隔符","来找，找到
: 指定个数以后就返回，但是这样如果start很靠后的话会需要很长时间，毕竟要O(L+M)
: 的时间。不知道有没有什么更优化的算法可以实现这样的功能？请各位大牛支招，多谢！
: 以下是我目前的实现代码：
: #include
| q*c
发帖数: 9453 | 14 就一次那根本没办法， 你这是要违反能量守恒定律的节奏啊。
【在 D********g 的大作中提到】
: 但是本身index comma位置的话就要O(N)了吧
| D********g
发帖数: 30 | 15 无他，就是为了考虑边界条件比如extractPartialString(whole, 2, 2)的话应该返回
空字串，否则的话把最后一个分隔符","给去掉。判断partialString.size()当然也可
以，就是多个条件判断了。
【在 N******K 的大作中提到】
: 你整这个干啥
: try {
: partialString.erase(partialString.size() - 1, 1);
: } catch (std::out_of_range & e) {
: cerr << "Out of range exception: " << e.what() << endl;
: }
: 判断一下partialString.size()不就行了
:
: 68,
: input
| c*********e
发帖数: 16335 | 16 这种题和工作以后处理的问题完全2码事。知道回字的5种写法后，就容易找工作了？
68,
input
谢！
【在 D********g 的大作中提到】
: 用C++写个函数，实现一个从一个长字符串里面找到一组子字符串的功能，但是不是一
: 般的子串，长字符串是一串由","分隔开的数字，比如"12,34,-54,65,367,-123,-9,68,
: "， 然后我的函数的signature是：
: string extractPartialString(const string& whole, int start, int end);
: 就是要找到在[start, end)之间的数字组成的子串。比如extractPartialString(input
: , 2, 5)应该返回子串"-54,65,367"。我就是直接一个一个的按照分隔符","来找，找到
: 指定个数以后就返回，但是这样如果start很靠后的话会需要很长时间，毕竟要O(L+M)
: 的时间。不知道有没有什么更优化的算法可以实现这样的功能？请各位大牛支招，多谢！
: 以下是我目前的实现代码：
: #include
| a*********a
发帖数: 3656 | 17 觉得这个逃不过O(N)，如果你要继续优化，只能从inner loop着手了。粗略看一下，可
能有一两个地方。要肯定，还是得上profiler，数instruction fetch.
1. while ((posNext = whole.find(',', posCurrent))
如果你自己用一个char*纪录在whole里的位置，可以避免find每次寻找posCurrent，我
估计是省掉一个指针加法。find()应该是先从whole的头进到posCurrent，然后步进找'
,'，这其中的第一步应该没有必要。
2. loop里面没有必要每次取elementStr = substr(...)，再加到partialString. 你的
code里没法保证没有多次的copy。如果partialString没有reserve够，可能还会有heap
realloc.
可以先找到start, stop position, 然后loop外做一次性substr。这样，可能还可以免
掉后来的erase。
这样下来，loop里面应该只有指针操作和字符比较。没有任何string操作。
68,
input
谢！
【在 D********g 的大作中提到】
: 用C++写个函数，实现一个从一个长字符串里面找到一组子字符串的功能，但是不是一
: 般的子串，长字符串是一串由","分隔开的数字，比如"12,34,-54,65,367,-123,-9,68,
: "， 然后我的函数的signature是：
: string extractPartialString(const string& whole, int start, int end);
: 就是要找到在[start, end)之间的数字组成的子串。比如extractPartialString(input
: , 2, 5)应该返回子串"-54,65,367"。我就是直接一个一个的按照分隔符","来找，找到
: 指定个数以后就返回，但是这样如果start很靠后的话会需要很长时间，毕竟要O(L+M)
: 的时间。不知道有没有什么更优化的算法可以实现这样的功能？请各位大牛支招，多谢！
: 以下是我目前的实现代码：
: #include
| n*****t
发帖数: 22014 | 18 你这个无论如何跑不了数逗号，唯一能想到的是把 string ptr 强制成 int64，先用
bitmask 扫，这样可以快将近 8 倍
【在 D********g 的大作中提到】
: 用C++写个函数，实现一个从一个长字符串里面找到一组子字符串的功能，但是不是一
: 般的子串，长字符串是一串由","分隔开的数字，比如"12,34,-54,65,367,-123,-9,68,
: "， 然后我的函数的signature是：
: string extractPartialString(const string& whole, int start, int end);
: 就是要找到在[start, end)之间的数字组成的子串。比如extractPartialString(input
: , 2, 5)应该返回子串"-54,65,367"。我就是直接一个一个的按照分隔符","来找，找到
: 指定个数以后就返回，但是这样如果start很靠后的话会需要很长时间，毕竟要O(L+M)
: 的时间。不知道有没有什么更优化的算法可以实现这样的功能？请各位大牛支招，多谢！
: 以下是我目前的实现代码：
: #include
| k**********g
发帖数: 989 | 19 用汇编可以快十六倍呢。
http://www.strchr.com/strcmp_and_strlen_using_sse_4.2
明明是数字，干嘛要用「人类可读格式」储存呢？
【在 n*****t 的大作中提到】
: 你这个无论如何跑不了数逗号，唯一能想到的是把 string ptr 强制成 int64，先用
: bitmask 扫，这样可以快将近 8 倍
| n*****t
发帖数: 22014 | 20 好像 libc 就是这么做的，我们都在瞎折腾，LOL
【在 k**********g 的大作中提到】
: 用汇编可以快十六倍呢。
: http://www.strchr.com/strcmp_and_strlen_using_sse_4.2
: 明明是数字，干嘛要用「人类可读格式」储存呢？
| w***x
发帖数: 105 | 21 弄个cache辅助下能加快点。
令 f(s, n) 是字符串s的第n个子串的结束位置。
那么你要求的 extractPartialString(s, a, b) = substr(s, f(s, a), f(s, a+b))
f(s, n)可以通过相邻的f(s, n-1) or f(s, n+1)来计算得出。 |
|
