История изменений

Исправление korvin_, 23.06.15 17:37 (текущая версия) :

Сам же написал, по ключам.

Но ты понимаешь, что в таком случае придётся не раз пройтись по коллекции ключей (1 раз в случае, если она хранится в хэше упорядоченной)? Т.е. я к тому, что создать список упорядоченных ключей отдельной функцией может быть вполне себе эффективным решением, кроме того такой вариант не блокирует хеш, используемый несколькими потоками.

рамках данной задачи, чтобы можно было параллельно сравнивать. Для большинства реализаций обход хэша быстрее,

Обход одного хэша и поиск ключа в другом, без необходимости сортировать коллекции ключей обоих хэшей.

Я уж не говорю о странности сравнения hasheq и hashequal.

По поводу тредов:

(define NCHANNELS 1000)
(define NTHREADS 10000)

(define channels (for/vector ((i (in-range NCHANNELS))) (make-channel)))

(define rand-gen (make-pseudo-random-generator))

(define (pick-channel)
  (let ((i (random NCHANNELS rand-gen)))
    (vector-ref channels i)))

(define (mixer)
  (define out (make-channel))
  (define n (- NCHANNELS 1))
  (define (loop)
    (let loop ((i 0))
      (when (channel-try-get (vector-ref channels i))
        (channel-put out #t))
      (loop (if (= i n) 0 (+ i 1)))))
  (thread loop)
  out)

(define (start-thread done)
  (thread
   (lambda ()
     (sleep 0.1)
     (channel-put done #t))))

(define (main)
  (define done (mixer))
  (for ((i (in-range NTHREADS)))
    (start-thread done))
  (for ((i (in-range NTHREADS)))
    (channel-get done))
  (displayln 'done))

(time (main))

-> Создать исполняемый файл -> Автономный (только для этого компьютера) -> База: Racket ->

done
cpu time: 1438 real time: 1438 gc time: 579

package main

import (
	"fmt"
	"math/rand"
	"time"
)

type signal struct{}

const (
	NCHANNELS = 1000
	NTHREADS  = 10000
)

var channels = func() []chan signal {
	c := make([]chan signal, NCHANNELS)
	for i := range c {
		c[i] = make(chan signal)
	}
	return c
}()

func pickChannel() chan signal {
	return channels[rand.Intn(NCHANNELS)]
}

func mixer() chan signal {
	return mixall(channels[0], channels[1:]...)
}

func startThread(done chan signal) {
	time.Sleep(time.Millisecond * 100)
	done <- signal{}
}

func main() {
	rand.Seed(time.Now().UnixNano())
	start := time.Now()
	realMain()
	fmt.Println(time.Since(start))
}

func realMain() {
	done := make(chan signal)
	for i := 0; i < NTHREADS; i++ {
		go startThread(done)
	}
	for i := 0; i < NTHREADS; i++ {
		<-done
	}
	fmt.Println("done")
}

func mixall(ch chan signal, rest ...chan signal) chan signal {
	for _, ch2 := range rest {
		ch = mix(ch, ch2)
	}
	return ch
}

func mix(ch1 chan signal, ch2 chan signal) chan signal {
	out := make(chan signal)
	go func() {
		for {
			select {
			case msg := <-ch1:
				out <- msg
			case msg := <-ch2:
				out <- msg
			}
		}
	}()
	return out
}

done
177.2589ms

Разница почти в 10 раз.

Возможно тест в чём-то не корректен, скажи, что можно и/или нужно исправить?

Исправление korvin_, 23.06.15 17:36:

Сам же написал, по ключам.

рамках данной задачи, чтобы можно было параллельно сравнивать. Для большинства реализаций обход хэша быстрее,

Обход одного хэша и поиск ключа в другом, без необходимости сортировать коллекции ключей обоих хэшей.

Я уж не говорю о странности сравнения hasheq и hashequal.

По поводу тредов:

(define NCHANNELS 1000)
(define NTHREADS 10000)

(define channels (for/vector ((i (in-range NCHANNELS))) (make-channel)))

(define rand-gen (make-pseudo-random-generator))

(define (pick-channel)
  (let ((i (random NCHANNELS rand-gen)))
    (vector-ref channels i)))

(define (mixer)
  (define out (make-channel))
  (define n (- NCHANNELS 1))
  (define (loop)
    (let loop ((i 0))
      (when (channel-try-get (vector-ref channels i))
        (channel-put out #t))
      (loop (if (= i n) 0 (+ i 1)))))
  (thread loop)
  out)

(define (start-thread done)
  (thread
   (lambda ()
     (sleep 0.1)
     (channel-put done #t))))

(define (main)
  (define done (mixer))
  (for ((i (in-range NTHREADS)))
    (start-thread done))
  (for ((i (in-range NTHREADS)))
    (channel-get done))
  (displayln 'done))

(time (main))

-> Создать исполняемый файл -> Автономный (только для этого компьютера) -> База: Racket ->

done
cpu time: 1438 real time: 1438 gc time: 579

package main

import (
	"fmt"
	"math/rand"
	"time"
)

type signal struct{}

const (
	NCHANNELS = 1000
	NTHREADS  = 10000
)

var channels = func() []chan signal {
	c := make([]chan signal, NCHANNELS)
	for i := range c {
		c[i] = make(chan signal)
	}
	return c
}()

func pickChannel() chan signal {
	return channels[rand.Intn(NCHANNELS)]
}

func mixer() chan signal {
	return mixall(channels[0], channels[1:]...)
}

func startThread(done chan signal) {
	time.Sleep(time.Millisecond * 100)
	done <- signal{}
}

func main() {
	rand.Seed(time.Now().UnixNano())
	start := time.Now()
	realMain()
	fmt.Println(time.Since(start))
}

func realMain() {
	done := make(chan signal)
	for i := 0; i < NTHREADS; i++ {
		go startThread(done)
	}
	for i := 0; i < NTHREADS; i++ {
		<-done
	}
	fmt.Println("done")
}

func send(ch chan string, message string) {
	time.Sleep(time.Duration(1+rand.Intn(250)) * time.Millisecond)
	ch <- message
}

func mixall(ch chan signal, rest ...chan signal) chan signal {
	for _, ch2 := range rest {
		ch = mix(ch, ch2)
	}
	return ch
}

func mix(ch1 chan signal, ch2 chan signal) chan signal {
	out := make(chan signal)
	go func() {
		for {
			select {
			case msg := <-ch1:
				out <- msg
			case msg := <-ch2:
				out <- msg
			}
		}
	}()
	return out
}

done
180.2676ms

Разница почти в 10 раз.

Возможно тест в чём-то не корректен, скажи, что можно и/или нужно исправить?

Исходная версия korvin_, 23.06.15 17:35:

Сам же написал, по ключам. Но ты понимаешь, что в таком случае придётся не раз пройтись по коллекции ключей (1 раз в случае, если она хранится в хэше упорядоченной)? Т.е. я к тому, что создать список упорядоченных ключей отдельной функцией может быть вполне себе эффективным решением, кроме того такой вариант не блокирует хеш, используемый несколькими потоками.

рамках данной задачи, чтобы можно было параллельно сравнивать. Для большинства реализаций обход хэша быстрее,

Обход одного хэша и поиск ключа в другом, без необходимости сортировать коллекции ключей обоих хэшей.

Я уж не говорю о странности сравнения hasheq и hashequal.

По поводу тредов:

(define NCHANNELS 1000)
(define NTHREADS 10000)

(define channels (for/vector ((i (in-range NCHANNELS))) (make-channel)))

(define rand-gen (make-pseudo-random-generator))

(define (pick-channel)
  (let ((i (random NCHANNELS rand-gen)))
    (vector-ref channels i)))

(define (mixer)
  (define out (make-channel))
  (define n (- NCHANNELS 1))
  (define (loop)
    (let loop ((i 0))
      (when (channel-try-get (vector-ref channels i))
        (channel-put out #t))
      (loop (if (= i n) 0 (+ i 1)))))
  (thread loop)
  out)

(define (start-thread done)
  (thread
   (lambda ()
     (sleep 0.1)
     (channel-put done #t))))

(define (main)
  (define done (mixer))
  (for ((i (in-range NTHREADS)))
    (start-thread done))
  (for ((i (in-range NTHREADS)))
    (channel-get done))
  (displayln 'done))

(time (main))

-> Создать исполняемый файл -> Автономный (только для этого компьютера) -> База: Racket ->

done
cpu time: 1438 real time: 1438 gc time: 579

package main

import (
	"fmt"
	"math/rand"
	"time"
)

type signal struct{}

const (
	NCHANNELS = 1000
	NTHREADS  = 10000
)

var channels = func() []chan signal {
	c := make([]chan signal, NCHANNELS)
	for i := range c {
		c[i] = make(chan signal)
	}
	return c
}()

func pickChannel() chan signal {
	return channels[rand.Intn(NCHANNELS)]
}

func mixer() chan signal {
	return mixall(channels[0], channels[1:]...)
}

func startThread(done chan signal) {
	time.Sleep(time.Millisecond * 100)
	done <- signal{}
}

func main() {
	rand.Seed(time.Now().UnixNano())
	start := time.Now()
	realMain()
	fmt.Println(time.Since(start))
}

func realMain() {
	done := make(chan signal)
	for i := 0; i < NTHREADS; i++ {
		go startThread(done)
	}
	for i := 0; i < NTHREADS; i++ {
		<-done
	}
	fmt.Println("done")
}

func send(ch chan string, message string) {
	time.Sleep(time.Duration(1+rand.Intn(250)) * time.Millisecond)
	ch <- message
}

func mixall(ch chan signal, rest ...chan signal) chan signal {
	for _, ch2 := range rest {
		ch = mix(ch, ch2)
	}
	return ch
}

func mix(ch1 chan signal, ch2 chan signal) chan signal {
	out := make(chan signal)
	go func() {
		for {
			select {
			case msg := <-ch1:
				out <- msg
			case msg := <-ch2:
				out <- msg
			}
		}
	}()
	return out
}

done
180.2676ms

Разница почти в 10 раз.

Возможно тест в чём-то не корректен, скажи, что можно и/или нужно исправить?