线程化:搜索值并停止所有线程 [英] threading: search for a value and stop all threads

问题描述

我需要实现一种搜索方法，该方法将搜索大海捞针并返回最初建立的needle索引.

I need to implement a search method that will search through haystack and return first founded index of needle.

静态整数搜索(T针，T []干草堆，整数numThreads)

static int search(T needle, T[] haystack, int numThreads)

我的问题:如果其中一个线程找到结果，如何停止所有线程?
例如:我正在搜索5，我在数组中有10个数字，使得[2，4，5，6，1，4，5，8，9，3]并有2个线程.因此，第一个线程将搜索第一部分[0-5)，第二个线程将搜索其他部分[5-10).如果线程2首先启动并且比其他线程更快地找到结果，则它应该返回6并终止线程1和2.

My question: How can I stop all threads if one of the thread finds result?
For example: I am searching for 5, I have 10 numbers in array such that [2, 4, 5, 6, 1, 4, 5, 8, 9, 3] and there are 2 threads. So first thread will look for first part [0 - 5), second thread will search other part [5 - 10). If thread 2 starts firstly and finds result quicker than other thread, it should return 6 and terminate thread 1 and 2.

推荐答案

做到这一点的经典方法是简单地在线程之间共享数据，以便它们可以相互通信.换句话说，在启动线程之前，将一些标志值初始化为未找到".

The classic way of doing this is to simply have shared data between the threads so that they can communicate with each other. In other words, initialise some flag value to "not found" before starting the threads.

然后，当线程运行时，它们处理数组中的元素，直到它们的元素用尽，或者或将标志值设置为"found".

Then, when the threads are running, they process elements in the array until either their elements are exhausted, or the flag value has been set to "found".

在伪代码中，类似于:

main():
    global array = createArray(size = 10000, values = random)
    global foundIndex = -1
    global mutex = createMutex()

    startThread(id = 1, func = threadFn, param = (0, 4999))
    startThread(id = 2, func = threadFn, param = (5000, 9999))

    waitFor(id = 1)
    waitFor(id = 2)

    print("Result is ", foundIndex)

threadFn(first, last):
    for index in first through last inclusive:
        if userSpecifiedCheckFound(array[index]):
            mutex.lock()
            if foundIndex == -1:
                foundIndex = index
            mutex.unlock()
            return

        mutex.lock()
        localIndex = foundIndex
        mutex.unlock()
        if localIndex != -1:
            return

您可以看到，该函数的每个实例都将设置共享数据，并在找到与所需条件相匹配的值时返回.如果另一个线程已经设置了共享数据，它也会 返回(不设置共享数据)，这意味着如果另一个线程已经找到了东西，它可以提早退出.

You can see from that that each instance of the function will set the shared data and return if it finds a value that matches whatever criteria you're looking for. It will also return (without setting the shared data) if another thread has already set the shared data, meaning it can exit early if another thread has already found something.

请记住，在这种情况下，需要保护共享数据foundIndex免受同时更改，以免损坏.在伪代码中，我展示了如何使用低级互斥信号量来实现这一目的.

Just keep in mind that the shared data, foundIndex in this case, needs to be protected from simultaneous changes lest it become corrupted. In the pseudo-code, I've shown how to do that with low-level mutual exclusion semaphores.

在Java中，这意味着使用synchronized可以达到相同的效果.举例来说，以下代码设置了一些合适的测试数据，以使二十单元阵列的第十六个单元满足搜索条件.

In Java, that means using synchronized to achieve the same effect. By way of example, the following code sets up some suitable test data so that the sixteenth cell of the twenty-cell array will satisfy the search criteria.

然后它运行两个线程，每个数据的一半，直到找到该单元格为止.

It then runs two threads, one on each half of the data, until it finds that cell.

public class TestProg extends Thread {
  // Shared data.

  static int [] sm_array = new int[20];
  static int sm_foundIndex = -1;

  // Each thread responsible for its own stuff.

  private int m_id, m_curr, m_last;
  public TestProg(int id, int first, int last) {
    m_id = id;
    m_curr = first;
    m_last = last;
  }

  // Runnable: continue until someone finds it.

  public void run() {
    // Try all cells allotted to thread.

    while (m_curr <= m_last) {
      System.out.println(m_id + ": processing " + m_curr);

      // If I find it first, save and exit.

      if (sm_array[m_curr] != 0) {
        synchronized(this) {
          if (sm_foundIndex == -1) {
            sm_foundIndex = m_curr;
            System.out.println(m_id + ": early exit, I found it");
            return;
          }
        }
      }

      // If someone else finds it, just exit.

      synchronized(this) {
        if (sm_foundIndex != -1) {
          System.out.println(m_id + ": early exit, sibling found it");
          return;
        }
      }

      // Kludge to ensure threads run side-by-side.

      try { Thread.sleep(100); } catch(Exception e) {}

      m_curr++;
    }
  }

  public static void main(String[] args) {
    // Create test data.

    for (int i = 0; i < 20; i++) {
      sm_array[i] = 0;
    }
    sm_array[15] = 1;

    // Create and start threads.

    HelloWorld thread1 = new HelloWorld(1, 0, 9);
    HelloWorld thread2 = new HelloWorld(2, 10, 19);
    thread1.start();
    thread2.start();

    // Wait for both to finish, then print result.

    try {
      thread1.join();
      thread2.join();
      System.out.println("=> Result was " + sm_foundIndex);
    } catch(Exception e) {
      System.out.println("Interrupted: " + e);
    }
  }
}

该代码的输出(尽管线程使它变得不确定)，

The output of that code (although threading makes it a little non-deterministic) is:

1: processing 0
2: processing 10
1: processing 1
2: processing 11
1: processing 2
2: processing 12
1: processing 3
2: processing 13
1: processing 4
2: processing 14
1: processing 5
2: processing 15
2: early exit, I found it
1: processing 6
1: early exit, sibling found it
=> Result was 15

这篇关于线程化:搜索值并停止所有线程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！