4 ms·

My first idea was to solve this "queue" (FIFO) problem with a "two stacks" solution: Without special system calls, files can only be appended and truncated at t

by adwn 6y ago

My first idea was to solve this "queue" (FIFO) problem with a "two stacks" solution: Without special system calls, files can only be appended and truncated at the end, not the beginning, so they behave like a stack. Two stacks can be used to simulate a queue. Implementation sketch: 1) Successively read the last 1 kiB from the source file, append it to a temporary file, and truncate 1 kiB from the source file. 2) Truncate the last 300M lines from the temporary file. 3) Successively read the last 1 kiB from the temporary file, append it to the destination file, and truncate 1 kiB from the temporary file. This way, you never need more than 1 kiB of additional disk space (tune this number as desired). I think this is an elegant solution. The correct solution, of course, is to buy a second disk.

bjornedstrom 6y ago
You win the internet today, that's a fantastic solution. I think the only gotcha is to handle the last block read in step 1 in case it's not evenly 1 kiB. Otherwise the first read in step 3 will overlap the blocks.
dasil003 6y ago
You should dub this “slinky copy”
anthropodie 6y ago
You must be pretty good at whiteboard interviews. I can pick up new technologies quickly and I am a good developer (at least my manager says so) but I can never come up with elegant solutions like this to what I call a whiteboard problem. This is the exact reason why I fail at those whiteboard interviews. Any suggestions for me?
- piva00 6y ago
  The only suggestion I have is practice, it's a skill like many others where practice makes you aware of patterns and these patterns have common or known approaches. Of course just blindly applying patterns won't cut it, the practice part is that the common ones become ingrained and you can focus your mental effort into the specifics of a new problem. Rehearsing your knowledge of data structures and algorithms while studying algorithmic quizzes can get you pretty far, it's time-consuming though so it needs to be something you get fun out of it, I don't get much fun out of it so I have done the bare minimum that is needed for this industry...
- adwn 6y ago
  > You must be pretty good at whiteboard interviews. I never had a single whiteboard interview in my life, so I can't give you advice on how to get better at them, sorry. Back in university, I had a "Design and Analysis of Algorithms" course, and one of the first (toy) exercises was to implement a queue using other data structures. This solution with two stacks was what I came up with. That's 12 years ago now, good times :-)
- jxcl 6y ago
  Maybe it's a whiteboard problem, but I would just call it a puzzle. Puzzle solving requires creativity. Picking up new technologies doesn't require creativity. Being a good developer (these days) also doesn't require much creativity, especially if you're just implementing spec and not designing systems. The best way to get better at puzzles is to practice puzzles! The reason I don't want to call these problems whiteboard problems is because it implies that they're only used in that context. These types of puzzles can be done for fun, too! Perhaps you start with simpler puzzles and try some simple solutions. You might solve a few. You'll try some harder puzzles and you'll get frustrated because the solution doesn't come immediately. Sometimes you'll combine two solutions you've used previously to solve something more complex. It's an amazing feeling! If you want a book of math puzzles, I recommend "Measurement" by Paul Lockhart. He explains and helps you explore math in the way he thinks it should be taught in schools, and I agree with him. If you want something more programming focused, take a look at "Programming Pearls" by Jon Bentley. It's a very old book, so the constraints he has to work with are quaint by today's standards (do something without using more than a megabyte of RAM. Hah!), but they're good puzzles as far as I remember. Good luck! Edit to add: The most useful thing you'll get from spending time with puzzles from a certain field is the intuition about which tools to reach for and which to forget about. You'll still likely have to try for a bunch of tools before you find the ones that work the best (or at all), but you'll get better at choosing ones that are more likely to work sooner, so you'll be able to progress faster on harder puzzles. As Greg LeMond said about cycling: ‘[It] never gets any easier, you just go faster’ :)
  - anthropodie 6y ago
    Thank for those recommendations!
dspillett 6y ago
> 1 kiB of additional disk space (tune this number as desired) Definitely tune that. The file-system is probably working in 4KiB blocks so there would be no benefit in working on smaller ones. In fact as you'll write to each block four times you are probably wasting a lot of time and causing more wear than you need to. I would suggest something far bigger (in the MiB range at least), especially on traditional drives where reducing head movements is key but random access latency on SSDs is not as close to zero as many people think particularly for small writes. Make sure that whatever you move the data with is loading that full block of your desired size into RAM before starting to write to the destination (i.e. perhaps pipe through something like "buffer -s 4M" if your read/write tool of choice does not support this directly). In fact an SSD might internally be working with MiB sized blocks, another reason to work in that scale at least and be careful of alignment where you can detect it or the lack of it. But yes, that solution would definitely work if carefully optimised. > The correct solution, of course, is to buy a second disk. Definitely. Must faster, and you still have the original data in-place so you can run checksums to verify the new copy before committing to use it.
- helltone 6y ago
  While filesystem block is usually 4k, I think ssd blocks are in the 256k-4mb range. So 4k is probably a bad choice.
  - dspillett 6y ago
    Aye, I mentioned that a bit further down. Also if working with network attached storage you have an extra set of considerations that will change the optimal block size to work with.
crote 6y ago
You can do it without a temporary file if your filesystem supports sparse files. Figure out the output size, and create a sparse file with that size. You'll be able to use it like a regular file, but blocks will only take up space once you write to them. Now simply copy from the input to the output file, starting at the end. Truncate the input file whenever the disk fills up.
pjc50 6y ago
Oh god, it's Towers of Hanoi with disk blocks.
hmpc 6y ago
Don't you need your read to be line-oriented to avoid breaking up lines?
- toast0 6y ago
  You might want to read from the source file line oriented until you find the start position of the first line to copy. Then copy from the end as described in large chunks (I would do 16Mb chunks assuming ram is sufficient). The sparse file suggestion a sibling made is really great. Otherwise, you could reverse the chunks as you write them, and end up with a fully reversed file, or just have to be careful about block boundaries and know that contents are forward, but blocks are backward. I wouldn't want to bulk read a 700g file with line processing, if it's possible to ignore that.
hamburglar 6y ago
I must be misunderstanding what you mean by "Truncate the last 300M lines from the temporary file" because it sounds like it would remove the only copy of the 1 kiB chunk on the first iteration.
- hamburglar 6y ago
  Oh, I think I see what you're doing here. Step 1 is actually an iteration over the entire file (I interpreted it as merely step 1 of a per-1k-block loop), effectively making a backwards (blockwise) copy of the original file but only using up 1kB of extra space at any given time. Step 2 is to truncate the "last" 300M lines, because those correspond to the first 300M lines of the original file. Step 3 is to re-reverse the temp file into the destination. This is great, although the line-vs-block-orientation issues will be tricky to make sure you get right, as others have pointed out. The truncate will almost certainly need to leave a partial last block.
svachalek 6y ago
I like this but there's a trick: reversing in blocks makes the last 300M "lines" not exactly the same as the first 300M lines of the source file. But the basic idea still works: You could read the original file forward to find the index of the 300M'th line, and then just halt the stack reversing bit when you get there. Delete the whole original file and then stack it back.

by adwn 6y ago

bjornedstrom 6y ago

You win the internet today, that's a fantastic solution. I think the only gotcha is to handle the last block read in step 1 in case it's not evenly 1 kiB. Otherwise the first read in step 3 will overlap the blocks.

dasil003 6y ago

You should dub this “slinky copy”

anthropodie 6y ago

You must be pretty good at whiteboard interviews. I can pick up new technologies quickly and I am a good developer (at least my manager says so) but I can never come up with elegant solutions like this to what I call a whiteboard problem. This is the exact reason why I fail at those whiteboard interviews. Any suggestions for me?

piva00 6y ago
The only suggestion I have is practice, it's a skill like many others where practice makes you aware of patterns and these patterns have common or known approaches. Of course just blindly applying patterns won't cut it, the practice part is that the common ones become ingrained and you can focus your mental effort into the specifics of a new problem. Rehearsing your knowledge of data structures and algorithms while studying algorithmic quizzes can get you pretty far, it's time-consuming though so it needs to be something you get fun out of it, I don't get much fun out of it so I have done the bare minimum that is needed for this industry...
adwn 6y ago
> You must be pretty good at whiteboard interviews. I never had a single whiteboard interview in my life, so I can't give you advice on how to get better at them, sorry. Back in university, I had a "Design and Analysis of Algorithms" course, and one of the first (toy) exercises was to implement a queue using other data structures. This solution with two stacks was what I came up with. That's 12 years ago now, good times :-)
jxcl 6y ago
Maybe it's a whiteboard problem, but I would just call it a puzzle. Puzzle solving requires creativity. Picking up new technologies doesn't require creativity. Being a good developer (these days) also doesn't require much creativity, especially if you're just implementing spec and not designing systems. The best way to get better at puzzles is to practice puzzles! The reason I don't want to call these problems whiteboard problems is because it implies that they're only used in that context. These types of puzzles can be done for fun, too! Perhaps you start with simpler puzzles and try some simple solutions. You might solve a few. You'll try some harder puzzles and you'll get frustrated because the solution doesn't come immediately. Sometimes you'll combine two solutions you've used previously to solve something more complex. It's an amazing feeling! If you want a book of math puzzles, I recommend "Measurement" by Paul Lockhart. He explains and helps you explore math in the way he thinks it should be taught in schools, and I agree with him. If you want something more programming focused, take a look at "Programming Pearls" by Jon Bentley. It's a very old book, so the constraints he has to work with are quaint by today's standards (do something without using more than a megabyte of RAM. Hah!), but they're good puzzles as far as I remember. Good luck! Edit to add: The most useful thing you'll get from spending time with puzzles from a certain field is the intuition about which tools to reach for and which to forget about. You'll still likely have to try for a bunch of tools before you find the ones that work the best (or at all), but you'll get better at choosing ones that are more likely to work sooner, so you'll be able to progress faster on harder puzzles. As Greg LeMond said about cycling: ‘[It] never gets any easier, you just go faster’ :)
- anthropodie 6y ago
  Thank for those recommendations!

dspillett 6y ago

> 1 kiB of additional disk space (tune this number as desired) Definitely tune that. The file-system is probably working in 4KiB blocks so there would be no benefit in working on smaller ones. In fact as you'll write to each block four times you are probably wasting a lot of time and causing more wear than you need to. I would suggest something far bigger (in the MiB range at least), especially on traditional drives where reducing head movements is key but random access latency on SSDs is not as close to zero as many people think particularly for small writes. Make sure that whatever you move the data with is loading that full block of your desired size into RAM before starting to write to the destination (i.e. perhaps pipe through something like "buffer -s 4M" if your read/write tool of choice does not support this directly). In fact an SSD might internally be working with MiB sized blocks, another reason to work in that scale at least and be careful of alignment where you can detect it or the lack of it. But yes, that solution would definitely work if carefully optimised. > The correct solution, of course, is to buy a second disk. Definitely. Must faster, and you still have the original data in-place so you can run checksums to verify the new copy before committing to use it.

helltone 6y ago
While filesystem block is usually 4k, I think ssd blocks are in the 256k-4mb range. So 4k is probably a bad choice.
- dspillett 6y ago
  Aye, I mentioned that a bit further down. Also if working with network attached storage you have an extra set of considerations that will change the optimal block size to work with.

crote 6y ago

You can do it without a temporary file if your filesystem supports sparse files. Figure out the output size, and create a sparse file with that size. You'll be able to use it like a regular file, but blocks will only take up space once you write to them. Now simply copy from the input to the output file, starting at the end. Truncate the input file whenever the disk fills up.

pjc50 6y ago

Oh god, it's Towers of Hanoi with disk blocks.

hmpc 6y ago

Don't you need your read to be line-oriented to avoid breaking up lines?

toast0 6y ago
You might want to read from the source file line oriented until you find the start position of the first line to copy. Then copy from the end as described in large chunks (I would do 16Mb chunks assuming ram is sufficient). The sparse file suggestion a sibling made is really great. Otherwise, you could reverse the chunks as you write them, and end up with a fully reversed file, or just have to be careful about block boundaries and know that contents are forward, but blocks are backward. I wouldn't want to bulk read a 700g file with line processing, if it's possible to ignore that.

hamburglar 6y ago

I must be misunderstanding what you mean by "Truncate the last 300M lines from the temporary file" because it sounds like it would remove the only copy of the 1 kiB chunk on the first iteration.

hamburglar 6y ago
Oh, I think I see what you're doing here. Step 1 is actually an iteration over the entire file (I interpreted it as merely step 1 of a per-1k-block loop), effectively making a backwards (blockwise) copy of the original file but only using up 1kB of extra space at any given time. Step 2 is to truncate the "last" 300M lines, because those correspond to the first 300M lines of the original file. Step 3 is to re-reverse the temp file into the destination. This is great, although the line-vs-block-orientation issues will be tricky to make sure you get right, as others have pointed out. The truncate will almost certainly need to leave a partial last block.

svachalek 6y ago

I like this but there's a trick: reversing in blocks makes the last 300M "lines" not exactly the same as the first 300M lines of the source file. But the basic idea still works: You could read the original file forward to find the index of the 300M'th line, and then just halt the stack reversing bit when you get there. Delete the whole original file and then stack it back.