Faster Shuffling?
I think the slowness here probably come from the fact that we are copying from and to python.

@lhoestq for all the `select`-based methods I think we should stay in Arrow format and update the writer so that it can accept Arrow tables or batches as well. What do you think? > @lhoestq for all the `select`-based methods I think we should stay in Arrow format and update the writer so that it can accept Arrow tables or batches as well. What do you think?

I just tried with `writer.write_table` with tables of 1000 elements and it's slower that the solution in #405 

On my side (select 10 000 examples):
- Original implementation: 12s
- Batched solution: 100ms
- solution using arrow tables: 350ms

I'll try with arrays and record batches to see if we can make it work. I tried using `.take` from pyarrow recordbatches but it doesn't improve the speed that much:
```python
import nlp
import numpy as np

dset = nlp.Dataset.from_file("dummy_test_select.arrow")  # dummy dataset with 100000 examples like {"a": "h"*512}
indices = np.random.randint(0, 100_000, 1000_000)
```

```python
%%time
batch_size = 10_000
writer = ArrowWriter(schema=dset.schema, path="dummy_path",
                     writer_batch_size=1000, disable_nullable=False)
for i in tqdm(range(0, len(indices), batch_size)):
    table = pa.concat_tables(dset._data.slice(int(i), 1) for i in indices[i : min(len(indices), i + batch_size)])
    batch = table.to_pydict()
    writer.write_batch(batch)
writer.finalize()
# 9.12s
```


```python
%%time
batch_size = 10_000
writer = ArrowWriter(schema=dset.schema, path="dummy_path", 
                     writer_batch_size=1000, disable_nullable=False)
for i in tqdm(range(0, len(indices), batch_size)):
    batch_indices = indices[i : min(len(indices), i + batch_size)]
    # First, extract only the indices that we need with a mask
    mask = [False] * len(dset)
    for k in batch_indices:
        mask[k] = True
    t_batch = dset._data.filter(pa.array(mask))
    # Second, build the list of indices for the filtered table, and taking care of duplicates
    rev_positions = {}
    duplicates = 0
    for i, j in enumerate(sorted(batch_indices)):
        if j in rev_positions:
            duplicates += 1
        else:
            rev_positions[j] = i - duplicates
    rev_map = [rev_positions[j] for j in batch_indices]
    # Third, use `.take` from the combined recordbatch
    t_combined = t_batch.combine_chunks()  # load in memory
    recordbatch = t_combined.to_batches()[0]
    table = pa.Table.from_arrays(
        [recordbatch[c].take(pa.array(rev_map)) for c in range(len(dset._data.column_names))],
        schema=writer.schema
    )
    writer.write_table(table)
writer.finalize()
# 3.2s
```
 Shuffling is now significantly faster thanks to #513 
Feel free to play with it now :)

Closing this one, but feel free to re-open if you have other questions
Consider shuffling bookcorpus:

```
dataset = nlp.load_dataset('bookcorpus', split='train')
dataset.shuffle()
```
According to tqdm, this will take around 2.5 hours on my machine to complete (even with the faster version of select from #405). I've also tried with `keep_in_memory=True` and `writer_batch_size=1000`.

But I can also just write the lines to a text file:

```
batch_size = 100000
with open('tmp.txt', 'w+') as out_f:
    for i in tqdm(range(0, len(dataset), batch_size)):
        batch = dataset[i:i+batch_size]['text']
        print("\n".join(batch), file=out_f)
```

Which completes in a couple minutes, followed by `shuf tmp.txt > tmp2.txt` which completes in under a minute. And finally,

```
dataset = nlp.load_dataset('text', data_files='tmp2.txt')
```

Which completes in under 10 minutes. I read up on Apache Arrow this morning, and it seems like the columnar data format is not especially well-suited to shuffling rows, since moving items around requires a lot of book-keeping. 

Is shuffle inherently slow, or am I just using it wrong? And if it is slow, would it make sense to try converting the data to a row-based format on disk and then shuffling? (Instead of calling select with a random permutation, as is currently done.)