-1

Lets assume I'm working with Python although it's not really relevant.

I have a big array and I want to find whether element x is in the array.

However, when one of the threads finds the element, I want that all other threads will stop,
there is no point for them to continue running. I want to continue with main program with the result.

What would be the right way for doing this? I want to minimize the cpu time of the other threads after I already found that the element is truly exist.

member555
  • 797
  • 1
  • 13
  • 40

2 Answers2

0

In Python, you can create a thread-safe queue in the main thread and pass it to each worker thread. Each worker should search while the queue is empty() and then terminate. If the result is found, the lucky worker should put() it into the queue, causing all other workers to stop after their current iteration.

Example code (untested):

from Queue import Queue
from Threading import Thread

class Worker(Thread):
    def __init__(self, queue):
        self.queue=queue

    def run(self):
        while self.queue.empty():
            result=search( ... )
            if result:
                queue.put(result)

def main():
    queue=Queue()
    workers=[]
    for i in xrange(0,5):
        workers.append(Worker(queue))
    result=queue.get()
    print result
Michael Jaros
  • 4,586
  • 1
  • 22
  • 39
  • Isn't it a "waste of time" to loop and check whether the queue is empty? It seems that other threads could continue searching at that time. Is there more elegant solution other than this one? – member555 Jan 27 '16 at 23:54
  • Am I right to assume that your objection boils down to the question whether a thread can be stopped at any time in contrast to having it terminate after its current iteration? Short answer: Doing so is discouraged. http://stackoverflow.com/questions/323972/is-there-any-way-to-kill-a-thread-in-python – Michael Jaros Jan 28 '16 at 00:04
  • So if I want to kill 10 threads like they suggested, I will have to iterate on them, but it's possible that in the middle of the iteration, one of the remaining threads will get control and will waste time(on searching). – member555 Jan 28 '16 at 00:16
  • If one search iteration is an expensive operation, you could think about splitting it up, checking the cancel condition multiple times during that operatoin. And instead of checking the queue in each worker, a cancel flag instance variable could be checked that is set by the main thread after reading the result (but I doubt this makes much difference). – Michael Jaros Jan 28 '16 at 00:21
  • I'm asking a theoretical question : how can I stop 10 threads in the best & right way? – member555 Jan 28 '16 at 14:34
  • The "right" way is to signal them (e.g. by using a thread-safe queue that is used for the results anyway as I have showed you, or by setting an instance variable) and let the workers terminate after checking that flag, which will often be at the beginning of an iteration. – Michael Jaros Jan 28 '16 at 15:30
0

There are multiple ways, one of them is polling a queue in caller's thread, where spawned threads store their results. As soon as there first result appears, terminate all running threads.

Just note, in CPython only one thread can run at the same time due to Global Interpreter Lock limitation (unless in C-extension which can free the lock). Also note, for searching in large data more appropriate data structure then array should be used, like a binary tree.

xblake
  • 1
  • 2