add Space character every 3 letters

dridk2

Hi,

I am making a DNA viewer which display sequence like a hexadecimal viewer.
So, I would like to add space every 3 letters in my QByteArray.

    QByteArray seq = "ACGTATAGTACGTACG"
    seq = transform(seq,3)
    seq = "ACG TAT AGT ACG TAC"

What the most efficient way to do that ? QString / QByteArray have many methods

Taz742

@dridk2

QByteArray seq = "ACGTATAGTACGTACG";

    int cnt = 0;

    for(int i = 3; i < seq.size() - 3; i++){
        if(i % 3 == 0){
            seq.insert(i + cnt++, ' ');
        }
    }

    qDebug() << seq; = "ACG TAT AGT ACG TAC G"

kshegunov

I don't know if it's efficient enough, but it's certainly a one-liner:

QString split = QString("ACGTATAGTACGTACG").replace(QRegularExpression("(.{3})"), "\\1 ");

Taz742

@kshegunov
Your code is small and effective.
My and your variant is probably the same in time?

VRonin

since you are using QByteArray (i.e. 1 character is 1 byte) you can probably optimise it using std::memcpy on the data() pointer.

QByteArray tarnsform(const QByteArray& seq, int span){
    if(seq.isEmpty() || span<=0) return QByteArray();
    const int oldArrSize = seq.size();
    QByteArray result(oldArrSize  + (oldArrSize /span) - (oldArrSize %span==0),' ');
    auto sourceIter = seq.cbegin();
    auto destIter = result.data();
    const auto srcEnd=seq.cend();
    for(int dstnc = std::distance(sourceIter,srcEnd);dstnc>0;dstnc-=span){
        std::memcpy(destIter,sourceIter,qMin(dstnc,span));
        destIter+=span+1;
        sourceIter+=span;
    }
    return result;
}

EDIT:

The code I had before broke memory if seq.size()%span!=0

kshegunov

@Taz742 said in add Space character every 3 letters:

My and your variant is probably the same in time?

I'd even speculate mine may be faster, even though it uses a regular expression. The problem with your piece of code is that at each insert of a new space you're copying the data after that position - the data has to be shifted, which might be rather heavy. The regular expression code (assuming it can optimize the expression well internally) can do it with a single memory allocation. In fact your code can be modified so it uses one allocation, by just using a resulting byte array and copying the data in chunks of 3 bytes, then setting a space, and then repeating.

Edit: My view hadn't updated, basically what @VRonin wrote is what I was talking about.

mrjj

Hi
Fast test. Might have logical issues. Just for fun.

using namespace std::chrono;
void MainWindow::on_pushButton_clicked() {
  high_resolution_clock::time_point t1 = high_resolution_clock::now();

  for (int var = 0; var < 10000; ++var) {
    int cnt = 0;
    QByteArray seq = "ACGTATAGTACGTACG";
    for(int i = 3; i < seq.size() - 3; i++) {
      if(i % 3 == 0) {
        seq.insert(i + cnt++, ' ');
      }
    }
  }
  high_resolution_clock::time_point t2 = high_resolution_clock::now();

  auto duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();

  qDebug() << "time: " << duration ;
}

void MainWindow::on_pushButton_2_clicked() {

  high_resolution_clock::time_point t1 = high_resolution_clock::now();

  for (int var = 0; var < 10000; ++var) {
    QString split = QString("ACGTATAGTACGTACG").replace(QRegularExpression("(.{3})"), "\\1 ");
  }
  high_resolution_clock::time_point t2 = high_resolution_clock::now();

  auto duration = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();

  qDebug() << "time QRegularExpression: " << duration ;
}

Result:
time: 9001
time: 8002
time: 8001
time: 8004
time: 8001
time: 8001
time: 7995
time: 8001
time: 8001
time: 8001
time QRegularExpression: 161033
time QRegularExpression: 162033
time QRegularExpression: 161032
time QRegularExpression: 161032
time QRegularExpression: 162032
time QRegularExpression: 162032
time QRegularExpression: 162033

VRonin

@mrjj Was that debug or release mode?

mrjj

@VRonin
both debug. ( but just ran it. not ran as debug)
You think it affects the result in uneven manner ??
I till try in release just to be sure.

Eeli K

@mrjj I think it's fair to optimize a bit:

QRegularExpression re{"(.{3})"};
high_resolution_clock::time_point t1 = high_resolution_clock::now();
...
...QString("ACGTATAGTACGTACG").replace(re, "\\1 ");

mrjj

@Eeli-K
Yes more fair to take out construction of "re"
I will try that also.

kshegunov

Designing benchmarking tests isn't exactly trivial, but I'd suggest something too (probably the raw insert will outperform the rx, but still for the sake of argument):

Don't use the same fixed size input string; use input that ranges from very short to very long. And do the benchmarking in batches e.g. run the same benchmark for at least 30-40 times and record the time for each run, then you'd get data that can be put into a histogram and you can work it statistically.

mrjj

@kshegunov
Yep varying input lengths might alter the result significantly so will try that too.

dridk2

Oh, I was not notify by email of all your answers ! Thanks a lot ! I will try it .
By the way, you can join the team for this small project !
https://github.com/labsquare/cuteFasta
Preview on twitter : https://twitter.com/labsquare/status/884146483406266368

reena jaus

try this : just modify ur for loop
i<seq.size()
thats it :- enjoy
QByteArray seq = "ACGTATAGTACGTACG";

int cnt = 0;

for(int i = 3; i < seq.size(); i++){
    if(i % 3 == 0){
        seq.insert(i + cnt++, ' ');
    }
}

qDebug() << seq; = "ACG TAT AGT ACG TAC G"