Algoritma menggambar garis cepat

9

Tugasnya adalah menemukan cara untuk menggambar garis horizontal dalam array bilangan bulat 16-bit.

Kami mengasumsikan array 256x192 piksel dengan 16 piksel per kata. Baris adalah proses yang berdekatan dari set (1) bit. Baris dapat dimulai di tengah kata apa pun, tumpang tindih dengan kata lain, dan diakhiri dengan kata apa pun; mereka juga dapat memulai dan mengakhiri kata yang sama. Mereka mungkin tidak melanjutkan ke baris berikutnya. Petunjuk: kata-kata tengahnya mudah - cukup tulis 0xffff, tetapi tepinya akan rumit, karena akan menangani kasing untuk awal dan akhir dalam kata yang sama. Fungsi / prosedur / rutin harus mengambil koordinat x0 dan x1 yang menunjukkan titik awal dan berhenti horizontal, serta koordinat.

Saya mengecualikan diri dari ini karena saya mendesain sendiri algoritma yang hampir identik untuk prosesor tertanam tapi saya ingin tahu bagaimana orang lain akan melakukannya. Poin bonus untuk menggunakan operasi yang relatif cepat (misalnya, operasi 64 bit atau operasi titik mengambang tidak akan cepat pada mesin yang disematkan tetapi pergeseran bit sederhana akan menjadi.)

fastest-code Thomas O
sumber
2
Codegolf adalah tentang kode pendek, bukan kode cepat atau mengoptimalkan kecepatan.
hallvabo
@hallvabo Solusi saya cukup pendek, sekitar 5 baris ketika batas memeriksa dan fitur tambahan (seperti mengubah piksel alih-alih mengaturnya.) dihapus.
Thomas O
9
@hallvabo, situs ini bukan hanya codegolf. Juga tentang mengoptimalkan kecepatan, tetapi tidak semua jenis optimisasi: bukan detail perangkat keras, tetapi kompleksitas algoritma.
Nakilon
@Nakilon: Saya tidak setuju. Lalu mengapa situs ini bernama Code Golf? Ada ribuan situs lain untuk kompleksitas algoritmik dan diskusi pengoptimalan kecepatan.
hallvabo
5
@hallvabo: Dari FAQ - "Code Golf - Stack Exchange adalah untuk pegolf kode dan bagi mereka yang tertarik dengan golf kode (dari pemula hingga pakar), dan teka-teki pemrograman." Saya menganggap ini sebagai teka-teki pemrograman.
Thomas O

Jawaban:

3

Kode ini mengasumsikan bahwa kedua x0 dan x1 adalah titik akhir inklusif, dan bahwa kata-kata adalah sedikit endian (yaitu, (0,0) pixel dapat diatur dengan array[0][0]|=1).

int line(word *array, int x0, int x1, int y) {
  word *line = array + (y << 4);
  word *start = line + (x0 >> 4);
  word *end = line + (x1 >> 4);
  word start_mask = (word)-1 << (x0 & 15);
  word end_mask = (unsigned word)-1 >> (15 - (x1 & 15));
  if (start == end) {
    *start |= start_mask & end_mask;
  } else {
    *start |= start_mask;
    *end |= end_mask;
    for (word *p = start + 1; p < end; p++) *p = (word)-1;
  }
}
Keith Randall
sumber
1
Seberapa cepat?
pengguna tidak diketahui
1

Python

Trik utama di sini adalah menggunakan tabel pencarian untuk menyimpan bitmask dari piksel. Ini menghemat beberapa operasi. Tabel 1kB tidak terlalu besar bahkan untuk platform tertanam saat ini

Jika ruang sangat ketat, untuk harga beberapa & 0xf tabel pencarian dapat dikurangi menjadi hanya 64B

Kode ini dalam Python, tetapi akan mudah untuk port ke bahasa apa pun yang mendukung operasi bit.

Jika menggunakan C, Anda bisa mempertimbangkan untuk melepas loop menggunakan switchdari perangkat Duff . Karena garis maksimum 16 kata lebar, saya akan memperpanjang switchhingga 14 baris dan membuang whilesemuanya.

T=[65535, 32767, 16383, 8191, 4095, 2047, 1023, 511,
   255, 127, 63, 31, 15, 7, 3, 1]*16
U=[32768, 49152, 57344, 61440, 63488, 64512, 65024, 65280,
   65408, 65472, 65504, 65520, 65528, 65532, 65534, 65535]*16

def drawline(x1,x2,y):
    y_=y<<4
    x1_=y_+(x1>>4)
    x2_=y_+(x2>>4)
    if x1_==x2_:
        buf[x1_]|=T[x1]&U[x2]
        return    
    buf[x1_]|=T[x1]
    buf[x2_]|=U[x2]        
    x1_+=+1
    while x1_<x2_:
        buf[x1_] = 0xffff
        x1_+=1


#### testing code ####

def clear():
    global buf
    buf=[0]*192*16

def render():
    for y in range(192):
        print "".join(bin(buf[(y<<4)+x])[2:].zfill(16) for x in range(16))


clear()
for y in range(0,192):
    drawline(y/2,y,y)
for x in range(10,200,6):
    drawline(x,x+2,0)
    drawline(x+3,x+5,1)
for y in range(-49,50):
    drawline(200-int((2500-y*y)**.5), 200+int((2500-y*y)**.5), y+60)
render()
gnibbler
sumber
1

Berikut ini adalah versi C dari jawaban Python saya menggunakan pernyataan switch alih-alih loop sementara dan mengurangi pengindeksan dengan menambahkan pointer bukan indeks array

Ukuran tabel pencarian dapat dikurangi secara substansial dengan menggunakan T [x1 & 0xf] dan U [x2 & 0xf] untuk beberapa instruksi tambahan

#include <stdio.h>
#include <math.h>

unsigned short T[] = {0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001,
                      0xffff, 0x7fff, 0x3fff, 0x1fff, 0x0fff, 0x07ff, 0x03ff, 0x01ff,
                      0x00ff, 0x007f, 0x003f, 0x001f, 0x000f, 0x0007, 0x0003, 0x0001};

unsigned short U[] = {0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
                      0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
                      0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff};

unsigned short buf[192*16];

void clear(){
    int i;
    for (i=0; i<192*16; i++) buf[i]==0;
}

void render(){
    int x,y;
    for (y=0; y<192; y++){
        for (x=0; x<256; x++) printf("%d", (buf[(y<<4)+(x>>4)]>>(15-(x&15)))&1);
        printf("\n");
    }
}

void drawline(int x1, int x2, int y){
    int y_ = y<<4;
    int x1_ = y_+(x1>>4);
    int x2_ = y_+(x2>>4);
    unsigned short *p = buf+x1_;

    if (x1_==x2_){
        *p|=T[x1]&U[x2];
        return;
        }

    *p++|=T[x1];
    switch (x2_-x1_){
    case 14: *p++ = 0xffff;
    case 13: *p++ = 0xffff;
    case 12: *p++ = 0xffff;
    case 11: *p++ = 0xffff;
    case 10: *p++ = 0xffff;
    case 9: *p++ = 0xffff;
    case 8: *p++ = 0xffff;
    case 7: *p++ = 0xffff;
    case 6: *p++ = 0xffff;
    case 5: *p++ = 0xffff;
    case 4: *p++ = 0xffff;
    case 3: *p++ = 0xffff;
    case 2: *p++ = 0xffff;
    case 1: *p++ = U[x2];
    }     
}


int main(){
    int x,y;
    clear();

    for (y=0; y<192; y++){
        drawline(y/2,y,y); 
    }

    for (x=10; x<200; x+=6){
        drawline(x,x+2,0);
        drawline(x+3,x+5,1);
    }

    for (y=-49; y<50; y++){
        x = sqrt(2500-y*y);
        drawline(200-x, 200+x, y+60);
    }
    render();
    return 0;
    }
gnibbler
sumber
Seberapa cepat?
pengguna tidak diketahui
@ pengguna tidak diketahui, Berapa lama seutas tali? Saya pikir itu harus lebih cepat daripada jawaban yang diterima karena menggunakan tabel pencarian untuk mengurangi jumlah pekerjaan sedikit. Mengapa Anda tidak mencobanya dan beri tahu kami apa yang Anda temukan?
gnibbler
1

Scala, 7s / 1M lines 4.1s / 1M lines

// declaration and initialisation of an empty field: 
val field = Array.ofDim[Short] (192, 16)

implementasi pertama: 

// util-method: set a single Bit:
def setBit (x: Int, y: Int) = 
  field (y)(x/16) = (field (y)(x/16) | (1 << (15 - (x % 16)))).toShort 
def line (x0: Int, x1: Int, y: Int) = 
  (x0 to x1) foreach (setBit (_ , y))

Setelah menghilangkan panggilan metode dalam, dan mengganti for-dengan loop-sementara, pada Core 2Ghz Tunggal saya dengan Scala 2.8 itu membebaskan 1 Mio. Baris dalam 4,1 detik. bukannya 7s awal.

  def line (x0: Int, x1: Int, y: Int) = {
    var x = x0
    while (x < x1) {  
      field (y)(x/16) = (field (y)(x/16) | (1 << (15 - (x % 16)))).toShort
      x += 1
    }
  }

Kode tes dan doa:

// sample invocation:
line (12, 39, 3) 
// verification 
def shortprint (s: Short) = s.toBinaryString.length match {          
  case 16 => s.toBinaryString                                          
  case 32 => s.toBinaryString.substring (16)                           
  case x  => ("0000000000000000".substring (x) + s.toBinaryString)}

field (3).take (5).foreach (s=> println (shortprint (s)))            
// result:
0000000000001111
1111111111111111
1111111100000000
0000000000000000
0000000000000000

Pengujian kinerja: 

  val r = util.Random 

  def testrow () {
    val a = r.nextInt (256)
    val b = r.nextInt (256)
    if (a < b)
      line (a, b, r.nextInt (192)) else
        line (b, a, r.nextInt (192)) 
  }

  def test (count: Int): Unit = {
    for (n <- (0 to count))
      testrow ()
  }

  // 1 mio tests
  test (1000*1000)

Diuji dengan waktu alat unix, membandingkan waktu pengguna, termasuk waktu startup, kode yang dikompilasi, tanpa fase memulai JVM.

Meningkatkan jumlah baris menunjukkan, bahwa untuk setiap juta baru, perlu 3.3s tambahan.

Pengguna tidak diketahui
sumber