

'''simple docstring'''







def  UpperCAmelCase__      ( )     ->     list[list[int]]:
       return [list(range(10_00 - i,    -10_00 - i,    -1			)			) for i in range(10_00			)]


__lowerCamelCase						    =      generate_large_matrix()
__lowerCamelCase						    =      (
    [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]],
    [[3, 2], [1, 0]],
    [[7, 7, 6]],
    [[7, 7, 6], [-1, -2, -3]],
    grid,
)
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     None:
       assert all(row == sorted(UpperCAmelCase__,    reverse=UpperCAmelCase__			) for row in grid			)
       assert all(list(UpperCAmelCase__			) == sorted(UpperCAmelCase__,    reverse=UpperCAmelCase__			) for col in zip(*UpperCAmelCase__			)			)
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     int:
       A_		   = 0
       A_		   = len(UpperCAmelCase__			) - 1

       # Edge cases such as no values or all numbers are negative.
       if not array or array[0] < 0:
              return 0

       while right + 1 > left:
              A_		   = (left + right) // 2
              A_		   = array[mid]

              # Num must be negative and the index must be greater than or equal to 0.
              if num < 0 and array[mid - 1] >= 0:
                     return mid

              if num >= 0:
                     A_		   = mid + 1
              else:
                     A_		   = mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
       return len(UpperCAmelCase__			)
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     int:
       A_		   = 0
       A_		   = len(grid[0]			)

       for i in range(len(UpperCAmelCase__			)			):
              A_		   = find_negative_index(grid[i][:bound]			)
              total += bound
       return (len(UpperCAmelCase__			) * len(grid[0]			)) - total
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     int:
       return len([number for row in grid for number in row if number < 0]			)
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     int:
       A_		   = 0
       for row in grid:
              for i, number in enumerate(UpperCAmelCase__			):
                     if number < 0:
                            total += len(UpperCAmelCase__			) - i
                            break
       return total
def  UpperCAmelCase__      ( )     ->     None:
       from timeit import timeit

       print("""Running benchmarks"""			)
       A_		   = (
           """from __main__ import count_negatives_binary_search, """
           """count_negatives_brute_force, count_negatives_brute_force_with_break, grid"""
       )
       for func in (
           "count_negatives_binary_search",  # took 0.7727 seconds
           "count_negatives_brute_force_with_break",  # took 4.6505 seconds
           "count_negatives_brute_force",  # took 12.8160 seconds
       ):
              A_		   = timeit(F'''{func}(grid=grid)''',    setup=UpperCAmelCase__,    number=5_00			)
              print(F'''{func}() took {time:0.4f} seconds'''			)


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      benchmark()



'''simple docstring'''







import json
import logging
import os
import socket

import git
import numpy as np
import torch


logging.basicConfig(
    format='''%(asctime)s - %(levelname)s - %(name)s - PID: %(process)d -  %(message)s''',
    datefmt='''%m/%d/%Y %H:%M:%S''',
    level=logging.INFO,
)
__lowerCamelCase						    =      logging.getLogger(__name__)
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     int:
       A_		   = git.Repo(search_parent_directories=UpperCAmelCase__			)
       A_		   = {
           """repo_id""": str(UpperCAmelCase__			),
           """repo_sha""": str(repo.head.object.hexsha			),
           """repo_branch""": str(repo.active_branch			),
       }

       with open(os.path.join(UpperCAmelCase__,    """git_log.json"""			),    """w"""			) as f:
              json.dump(UpperCAmelCase__,    UpperCAmelCase__,    indent=4			)
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     Dict:
       if params.n_gpu <= 0:
              A_		   = 0
              A_		   = -1
              A_		   = True
              A_		   = False
              return

       assert torch.cuda.is_available()

       logger.info("""Initializing GPUs"""			)
       if params.n_gpu > 1:
              assert params.local_rank != -1

              A_		   = int(os.environ["""WORLD_SIZE"""]			)
              A_		   = int(os.environ["""N_GPU_NODE"""]			)
              A_		   = int(os.environ["""RANK"""]			)

              # number of nodes / node ID
              A_		   = params.world_size // params.n_gpu_per_node
              A_		   = params.global_rank // params.n_gpu_per_node
              A_		   = True

              assert params.n_nodes == int(os.environ["""N_NODES"""]			)
              assert params.node_id == int(os.environ["""NODE_RANK"""]			)

       # local job (single GPU)
       else:
              assert params.local_rank == -1

              A_		   = 1
              A_		   = 0
              A_		   = 0
              A_		   = 0
              A_		   = 1
              A_		   = 1
              A_		   = False

       # sanity checks
       assert params.n_nodes >= 1
       assert 0 <= params.node_id < params.n_nodes
       assert 0 <= params.local_rank <= params.global_rank < params.world_size
       assert params.world_size == params.n_nodes * params.n_gpu_per_node

       # define whether this is the master process / if we are in multi-node distributed mode
       A_		   = params.node_id == 0 and params.local_rank == 0
       A_		   = params.n_nodes > 1

       # summary
       A_		   = F'''--- Global rank: {params.global_rank} - '''
       logger.info(PREFIX + """Number of nodes: %i""" % params.n_nodes			)
       logger.info(PREFIX + """Node ID        : %i""" % params.node_id			)
       logger.info(PREFIX + """Local rank     : %i""" % params.local_rank			)
       logger.info(PREFIX + """World size     : %i""" % params.world_size			)
       logger.info(PREFIX + """GPUs per node  : %i""" % params.n_gpu_per_node			)
       logger.info(PREFIX + """Master         : %s""" % str(params.is_master			)			)
       logger.info(PREFIX + """Multi-node     : %s""" % str(params.multi_node			)			)
       logger.info(PREFIX + """Multi-GPU      : %s""" % str(params.multi_gpu			)			)
       logger.info(PREFIX + """Hostname       : %s""" % socket.gethostname()			)

       # set GPU device
       torch.cuda.set_device(params.local_rank			)

       # initialize multi-GPU
       if params.multi_gpu:
              logger.info("""Initializing PyTorch distributed"""			)
              torch.distributed.init_process_group(
                  init_method="""env://""",    backend="""nccl""",    )







def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     Tuple:
       np.random.seed(args.seed			)
       torch.manual_seed(args.seed			)
       if args.n_gpu > 0:
              torch.cuda.manual_seed_all(args.seed			)
