Reversing QString and QByteArray

[alrawab]

hi
What is the best way to get reverse of QString and QByteArray (fast and safe) with out using loops (it becomes very slow with huge data)
thanks
Br
Sis

[Santosh Reddy]

If you don't want to maintain loops, then may be you can maintain a copy of reverse. I mean a parallel copy. Each time you do an append on the string, do the similar reversed operation of the other copy. Tricky

[alrawab]

yes it a good idea but i'm dealing with dna sequences .
i'm using :
for( QByteArray::const_iterator i = myqbyte.constEnd(); i !=myqbyte.constBegin(); )
but this procedure become so slow with large sequences

[Santosh Reddy]

DNA

I were to do so, I would write a customized container for DNA strand/sequence, (This will need knowledge of DNA structure and ways to digitize it)

There are other methods, but are applciation specific, like reverse only the section of the sequence? (instead of complete sequence).

Think again do you really want to reverse the sequence? can you not re-write your operation to operate on the sequence in reverse (I bet that should be acceptable)

[alrawab]

this is my function which do the reverse task (some time i need to get the reverse of the full length )
//--------------------------------------
// Returns the reverse strand of a DNA or RNA sequence.
QByteArray QDnaSequence::Reverse(QByteArray& seq)
{
QByteArray reverse;
for( QByteArray::const_iterator i = seq.constEnd(); i !=seq.constBegin(); )
{
--i;
reverse += *i;
}
return reverse;
}

[wysota]

There is std::reverse(), you know...

#include <algorithm>
 
QByteArray reverse = seq;
std::reverse(reverse.constBegin(), reverse.constEnd());

#include <algorithm>

QByteArray reverse = seq;
std::reverse(reverse.constBegin(), reverse.constEnd());

To copy to clipboard, switch view to plain text mode 

You can also use reverse_copy:

QByteArray reverse;
std::reverse_copy(seq.constBegin(), seq.constEnd(), reverse.begin());

QByteArray reverse;
std::reverse_copy(seq.constBegin(), seq.constEnd(), reverse.begin());

To copy to clipboard, switch view to plain text mode 

Complexity is O(n).

There is also the trivial approach:

QByteArray reverse(const QByteArray &ba) {
  QByteArray reverse;
  reverse.reserve(ba.size());
  for(int i=ba.size(); i>=0; --i) reverse.append(ba.at(i));
  return reverse;
}

QByteArray reverse(const QByteArray &ba) {
  QByteArray reverse;
  reverse.reserve(ba.size());
  for(int i=ba.size(); i>=0; --i) reverse.append(ba.at(i));
  return reverse;
}

To copy to clipboard, switch view to plain text mode 

I can also imagine parallelizing the algorithm by dividing the array into chunks and reversing each chunk in a separate thread.

---

Added after 21 minutes:

Here is a complete implementation:

#include <QByteArray>
 
#include <QtConcurrentMap>
 
struct Chunk {
  char *ba;
  int size;
  int from;
  int cnt;
};
 
void swapChunk(const Chunk &ch) {
  const int size = ch.size;
  char *baRef = ch.ba;
  for(int i=0;i<ch.cnt;++i) {
    int i1 = ch.from+i;
    int i2 = size-1-ch.from-i;
    qSwap(baRef[i1], baRef[i2]);    
  }
}
 
QByteArray reverseInParallel(QByteArray ba) {
  char *dat = ba.data();
  int threads = QThread::idealThreadCount();
  int bytesPerThread = ba.size()/2/threads; // if size not even, the middle doesn't change anyway
  // prepare work
  QList<Chunk> chunks;
  for(int i=0;i<threads;++i) {
    Chunk ch;
    ch.ba = dat;
    ch.size = ba.size();
    ch.from = bytesPerThread*i;
    ch.cnt = bytesPerThread;
    chunks << ch;
  }
  // execute
  QtConcurrent::blockingMap(chunks, swapChunk);
  return ba;
}
 
int main() {
  QByteArray ba;
  for(int i=0;i<10;++i) {
    ba += "0123456789";
  }
  qDebug() << reverseInParallel(ba);
  return 0;
}

#include <QByteArray>

#include <QtConcurrentMap>

struct Chunk {
  char *ba;
  int size;
  int from;
  int cnt;
};

void swapChunk(const Chunk &ch) {
  const int size = ch.size;
  char *baRef = ch.ba;
  for(int i=0;i<ch.cnt;++i) {
    int i1 = ch.from+i;
    int i2 = size-1-ch.from-i;
    qSwap(baRef[i1], baRef[i2]);    
  }
}

QByteArray reverseInParallel(QByteArray ba) {
  char *dat = ba.data();
  int threads = QThread::idealThreadCount();
  int bytesPerThread = ba.size()/2/threads; // if size not even, the middle doesn't change anyway
  // prepare work
  QList<Chunk> chunks;
  for(int i=0;i<threads;++i) {
    Chunk ch;
    ch.ba = dat;
    ch.size = ba.size();
    ch.from = bytesPerThread*i;
    ch.cnt = bytesPerThread;
    chunks << ch;
  }
  // execute
  QtConcurrent::blockingMap(chunks, swapChunk);
  return ba;
}

int main() {
  QByteArray ba;
  for(int i=0;i<10;++i) {
    ba += "0123456789";
  }
  qDebug() << reverseInParallel(ba);
  return 0;
}

To copy to clipboard, switch view to plain text mode 

[alrawab]

There is std::reverse()
i know my question concerning is there pure Qt procedure to do that with out usin std
thanks a lot

[wysota]

Using what the C++ language offers doesn't make you "less Qt". That's often a newbie mistake to search for "Qt solutions" if they already have C++ solutions. You can't program Qt without C++.