4 ms·

What if you receive the same tweet 3 days later? It should only be counted once.

by cdoxsey 8y ago

ikeboy 8y ago
You dedup against the old data. Easier than deduping a month's worth all at once, since the old data is sorted.
- Jupe 8y ago
  Or just don't record it until it's successful. Logging attempts (and billing for them) doesn't seem like a good idea.
  - hinkley 8y ago
    More precisely: logging attempts might have business value, but not to the billing department. Log your confirmations too.
- cdoxsey 8y ago
  Sorry what I'm getting at is you can't do this problem incrementally. You can't calculate the count on day 1 and add it to the count on day 2. The count of each day is intertwined with all the others. But yes I suppose if at the end of each day you deduped that days records against the rest of the month you could then add them all together. Unfortunately day 30 would still be just as bad as doing the whole month, since removing duplicates is as expensive as counting uniques.
  - ikeboy 8y ago
    >removing duplicates is as expensive as counting uniques. I don't think so. You do all kinds of things (unzip, sort, uniq, plus apparently 1-2 passes through the whole data). If you did it daily, you only need to dedup day 30 vs a sorted version of the rest of the month, which takes around a 30th of the time, and you don't need to unzip/sort/uniq 29/30ths worth of data. I don't know your exact structure but I don't see why most of the computation can't be done earlier. Think of it this way: on day 30 with the script described in the post, for the first $X amount of time you're reading the beginning of the files and don't touch any day 30 data until later in those 16 hours. So there's definitely some kind of processing that could be done prior to day 30.
  - ikeboy 8y ago
    Deduping a file of size X/30 against a sorted file of size X should take time (X/30) * log x * n, since the lookups benefit from binary search due to the sort and you only need to do X/30 of the lookups. This should be significantly smaller, by a factor of 10 at least and likely a factor of 30, vs sorting X records. You probably have the same Big O but doing it on less data.

What if you receive the same tweet 3 days later? It should only be counted once.

ikeboy 8y ago

You dedup against the old data. Easier than deduping a month's worth all at once, since the old data is sorted.

Jupe 8y ago
Or just don't record it until it's successful. Logging attempts (and billing for them) doesn't seem like a good idea.
- hinkley 8y ago
  More precisely: logging attempts might have business value, but not to the billing department. Log your confirmations too.
cdoxsey 8y ago
Sorry what I'm getting at is you can't do this problem incrementally. You can't calculate the count on day 1 and add it to the count on day 2. The count of each day is intertwined with all the others. But yes I suppose if at the end of each day you deduped that days records against the rest of the month you could then add them all together. Unfortunately day 30 would still be just as bad as doing the whole month, since removing duplicates is as expensive as counting uniques.
- ikeboy 8y ago
  >removing duplicates is as expensive as counting uniques. I don't think so. You do all kinds of things (unzip, sort, uniq, plus apparently 1-2 passes through the whole data). If you did it daily, you only need to dedup day 30 vs a sorted version of the rest of the month, which takes around a 30th of the time, and you don't need to unzip/sort/uniq 29/30ths worth of data. I don't know your exact structure but I don't see why most of the computation can't be done earlier. Think of it this way: on day 30 with the script described in the post, for the first $X amount of time you're reading the beginning of the files and don't touch any day 30 data until later in those 16 hours. So there's definitely some kind of processing that could be done prior to day 30.
- ikeboy 8y ago
  Deduping a file of size X/30 against a sorted file of size X should take time (X/30) * log x * n, since the lookups benefit from binary search due to the sort and you only need to do X/30 of the lookups. This should be significantly smaller, by a factor of 10 at least and likely a factor of 30, vs sorting X records. You probably have the same Big O but doing it on less data.