


'''simple docstring'''



def      _a     (						):





     '''simple docstring'''






     return [list(range(1000 - i      , -1000 - i      , -1  )  ) for i in range(1000  )]


__UpperCAmelCase      :Union[str, Any]			    =       generate_large_matrix()
__UpperCAmelCase      :List[Any]			    =       (
    [[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      _a     (						_lowercase :     list[list[int]]  ):





     '''simple docstring'''






     assert all(row == sorted(_lowercase      , reverse=_lowercase  ) for row in grid  )
     assert all(list(_lowercase  ) == sorted(_lowercase      , reverse=_lowercase  ) for col in zip(*_lowercase  )  )




def      _a     (						_lowercase :     list[int]  ):





     '''simple docstring'''






     __UpperCAmelCase     :			Optional[int]  							=      0
     __UpperCAmelCase     :			Dict  							=      len(_lowercase  ) - 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:
          __UpperCAmelCase     :			str  							=      (left + right) // 2
          __UpperCAmelCase     :			Optional[int]  							=      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:
               __UpperCAmelCase     :			Union[str, Any]  							=      mid + 1
          else:
               __UpperCAmelCase     :			Any  							=      mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
     return len(_lowercase  )




def      _a     (						_lowercase :     list[list[int]]  ):





     '''simple docstring'''






     __UpperCAmelCase     :			List[Any]  							=      0
     __UpperCAmelCase     :			Optional[int]  							=      len(grid[0]  )

     for i in range(len(_lowercase  )  ):
          __UpperCAmelCase     :			Dict  							=      find_negative_index(grid[i][:bound]  )
          total += bound
     return (len(_lowercase  ) * len(grid[0]  )) - total




def      _a     (						_lowercase :     list[list[int]]  ):





     '''simple docstring'''






     return len([number for row in grid for number in row if number < 0]  )




def      _a     (						_lowercase :     list[list[int]]  ):





     '''simple docstring'''






     __UpperCAmelCase     :			Union[str, Any]  							=      0
     for row in grid:
          for i, number in enumerate(_lowercase  ):
               if number < 0:
                    total += len(_lowercase  ) - i
                    break
     return total




def      _a     (						):





     '''simple docstring'''






     from timeit import timeit

     print('''Running benchmarks'''  )
     __UpperCAmelCase     :			Dict  							=      (
         '''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
     ):
          __UpperCAmelCase     :			Tuple  							=      timeit(F'{func}(grid=grid)'      , setup=_lowercase      , number=500  )
          print(F'{func}() took {time:0.4f} seconds'  )


if __name__ == "__main__":
      import doctest

      doctest.testmod()
      benchmark()



'''simple docstring'''



import argparse

import torch

from transformers import BlenderbotConfig, BlenderbotForConditionalGeneration
from transformers.utils import logging


logging.set_verbosity_info()
__UpperCAmelCase      :Any			    =       logging.get_logger(__name__)

__UpperCAmelCase      :Dict			    =       [
    ["attention", "attn"],
    ["encoder_attention", "encoder_attn"],
    ["q_lin", "q_proj"],
    ["k_lin", "k_proj"],
    ["v_lin", "v_proj"],
    ["out_lin", "out_proj"],
    ["norm_embeddings", "layernorm_embedding"],
    ["position_embeddings", "embed_positions"],
    ["embeddings", "embed_tokens"],
    ["ffn.lin", "fc"],
]




def      _a     (						_lowercase :     Tuple  ):





     '''simple docstring'''






     if k == "embeddings.weight":
          return "shared.weight"

     for parlai_name, hf_name in PATTERNS:
          __UpperCAmelCase     :			Any  							=      k.replace(_lowercase      , _lowercase  )

     if k.startswith('''encoder'''  ):
          __UpperCAmelCase     :			str  							=      k.replace('''.attn'''      , '''.self_attn'''  )
          __UpperCAmelCase     :			Any  							=      k.replace('''norm1'''      , '''self_attn_layer_norm'''  )
          __UpperCAmelCase     :			List[str]  							=      k.replace('''norm2'''      , '''final_layer_norm'''  )
     elif k.startswith('''decoder'''  ):
          __UpperCAmelCase     :			int  							=      k.replace('''norm1'''      , '''self_attn_layer_norm'''  )
          __UpperCAmelCase     :			Union[str, Any]  							=      k.replace('''norm2'''      , '''encoder_attn_layer_norm'''  )
          __UpperCAmelCase     :			List[Any]  							=      k.replace('''norm3'''      , '''final_layer_norm'''  )
     return k




def      _a     (						_lowercase :     Union[str, Any]  ):





     '''simple docstring'''






     __UpperCAmelCase     :			int  							=      [
         '''model.encoder.layernorm_embedding.weight''',
         '''model.encoder.layernorm_embedding.bias''',
         '''model.decoder.layernorm_embedding.weight''',
         '''model.decoder.layernorm_embedding.bias''',
     ]
     for k in keys:
          __UpperCAmelCase     :			Any  							=      sd.pop(_lowercase  )
          __UpperCAmelCase     :			Optional[int]  							=      k.replace('''layernorm_embedding'''      , '''layer_norm'''  )
          assert new_k not in sd
          __UpperCAmelCase     :			List[str]  							=      v


__UpperCAmelCase      :str			    =       ["START"]




@torch.no_grad()
def      _a     (						_lowercase :     Optional[int]      , _lowercase :     Optional[int]      , _lowercase :     str  ):





     '''simple docstring'''






     __UpperCAmelCase     :			Any  							=      torch.load(_lowercase      , map_location='''cpu'''  )
     __UpperCAmelCase     :			List[str]  							=      model['''model''']
     __UpperCAmelCase     :			Optional[Any]  							=      BlenderbotConfig.from_json_file(_lowercase  )
     __UpperCAmelCase     :			Optional[Any]  							=      BlenderbotForConditionalGeneration(_lowercase  )
     __UpperCAmelCase     :			Optional[Any]  							=      m.model.state_dict().keys()
     __UpperCAmelCase     :			int  							=      []
     __UpperCAmelCase     :			List[str]  							=      {}
     for k, v in sd.items():
          if k in IGNORE_KEYS:
               continue

          __UpperCAmelCase     :			int  							=      rename_state_dict_key(_lowercase  )
          if new_k not in valid_keys:
               failures.append([k, new_k]  )
          else:
               __UpperCAmelCase     :			Union[str, Any]  							=      v
     if cfg.normalize_before:  # Blenderbot-3B checkpoints. Rename layernorm_embedding -> layer_norm
          rename_layernorm_keys(_lowercase  )
     m.model.load_state_dict(_lowercase      , strict=_lowercase  )
     m.half()
     m.save_pretrained(_lowercase  )


if __name__ == "__main__":
      __UpperCAmelCase      :Optional[int]			    =       argparse.ArgumentParser()
      # Required parameters
      parser.add_argument("--src_path", type=str, help="like blenderbot-model.bin")
      parser.add_argument("--save_dir", default="hf_blenderbot", type=str, help="Where to save converted model.")
      parser.add_argument(
          "--hf_config_json", default="blenderbot-3b-config.json", type=str, help="Path to config to use"
      )
      __UpperCAmelCase      :Tuple			    =       parser.parse_args()
      convert_parlai_checkpoint(args.src_path, args.save_dir, args.hf_config_json)